bitmap.c 40 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476
  1. /*
  2. * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
  3. */
  4. /* Reiserfs block (de)allocator, bitmap-based. */
  5. #include <linux/time.h>
  6. #include "reiserfs.h"
  7. #include <linux/errno.h>
  8. #include <linux/buffer_head.h>
  9. #include <linux/kernel.h>
  10. #include <linux/pagemap.h>
  11. #include <linux/vmalloc.h>
  12. #include <linux/quotaops.h>
  13. #include <linux/seq_file.h>
  14. #define PREALLOCATION_SIZE 9
  15. /* different reiserfs block allocator options */
  16. #define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
  17. #define _ALLOC_concentrating_formatted_nodes 0
  18. #define _ALLOC_displacing_large_files 1
  19. #define _ALLOC_displacing_new_packing_localities 2
  20. #define _ALLOC_old_hashed_relocation 3
  21. #define _ALLOC_new_hashed_relocation 4
  22. #define _ALLOC_skip_busy 5
  23. #define _ALLOC_displace_based_on_dirid 6
  24. #define _ALLOC_hashed_formatted_nodes 7
  25. #define _ALLOC_old_way 8
  26. #define _ALLOC_hundredth_slices 9
  27. #define _ALLOC_dirid_groups 10
  28. #define _ALLOC_oid_groups 11
  29. #define _ALLOC_packing_groups 12
  30. #define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
  31. #define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
  32. #define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
  33. #define SET_OPTION(optname) \
  34. do { \
  35. reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \
  36. set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
  37. } while(0)
  38. #define TEST_OPTION(optname, s) \
  39. test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
  40. static inline void get_bit_address(struct super_block *s,
  41. b_blocknr_t block,
  42. unsigned int *bmap_nr,
  43. unsigned int *offset)
  44. {
  45. /*
  46. * It is in the bitmap block number equal to the block
  47. * number divided by the number of bits in a block.
  48. */
  49. *bmap_nr = block >> (s->s_blocksize_bits + 3);
  50. /* Within that bitmap block it is located at bit offset *offset. */
  51. *offset = block & ((s->s_blocksize << 3) - 1);
  52. }
  53. int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value)
  54. {
  55. unsigned int bmap, offset;
  56. unsigned int bmap_count = reiserfs_bmap_count(s);
  57. if (block == 0 || block >= SB_BLOCK_COUNT(s)) {
  58. reiserfs_error(s, "vs-4010",
  59. "block number is out of range %lu (%u)",
  60. block, SB_BLOCK_COUNT(s));
  61. return 0;
  62. }
  63. get_bit_address(s, block, &bmap, &offset);
  64. /*
  65. * Old format filesystem? Unlikely, but the bitmaps are all
  66. * up front so we need to account for it.
  67. */
  68. if (unlikely(test_bit(REISERFS_OLD_FORMAT,
  69. &REISERFS_SB(s)->s_properties))) {
  70. b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1;
  71. if (block >= bmap1 &&
  72. block <= bmap1 + bmap_count) {
  73. reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) "
  74. "can't be freed or reused",
  75. block, bmap_count);
  76. return 0;
  77. }
  78. } else {
  79. if (offset == 0) {
  80. reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) "
  81. "can't be freed or reused",
  82. block, bmap_count);
  83. return 0;
  84. }
  85. }
  86. if (bmap >= bmap_count) {
  87. reiserfs_error(s, "vs-4030", "bitmap for requested block "
  88. "is out of range: block=%lu, bitmap_nr=%u",
  89. block, bmap);
  90. return 0;
  91. }
  92. if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) {
  93. reiserfs_error(s, "vs-4050", "this is root block (%u), "
  94. "it must be busy", SB_ROOT_BLOCK(s));
  95. return 0;
  96. }
  97. return 1;
  98. }
  99. /*
  100. * Searches in journal structures for a given block number (bmap, off).
  101. * If block is found in reiserfs journal it suggests next free block
  102. * candidate to test.
  103. */
  104. static inline int is_block_in_journal(struct super_block *s, unsigned int bmap,
  105. int off, int *next)
  106. {
  107. b_blocknr_t tmp;
  108. if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) {
  109. if (tmp) { /* hint supplied */
  110. *next = tmp;
  111. PROC_INFO_INC(s, scan_bitmap.in_journal_hint);
  112. } else {
  113. (*next) = off + 1; /* inc offset to avoid looping. */
  114. PROC_INFO_INC(s, scan_bitmap.in_journal_nohint);
  115. }
  116. PROC_INFO_INC(s, scan_bitmap.retry);
  117. return 1;
  118. }
  119. return 0;
  120. }
  121. /*
  122. * Searches for a window of zero bits with given minimum and maximum
  123. * lengths in one bitmap block
  124. */
  125. static int scan_bitmap_block(struct reiserfs_transaction_handle *th,
  126. unsigned int bmap_n, int *beg, int boundary,
  127. int min, int max, int unfm)
  128. {
  129. struct super_block *s = th->t_super;
  130. struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n];
  131. struct buffer_head *bh;
  132. int end, next;
  133. int org = *beg;
  134. BUG_ON(!th->t_trans_id);
  135. RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of "
  136. "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1);
  137. PROC_INFO_INC(s, scan_bitmap.bmap);
  138. if (!bi) {
  139. reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer "
  140. "for bitmap %d", bmap_n);
  141. return 0;
  142. }
  143. bh = reiserfs_read_bitmap_block(s, bmap_n);
  144. if (bh == NULL)
  145. return 0;
  146. while (1) {
  147. cont:
  148. if (bi->free_count < min) {
  149. brelse(bh);
  150. return 0; /* No free blocks in this bitmap */
  151. }
  152. /* search for a first zero bit -- beginning of a window */
  153. *beg = reiserfs_find_next_zero_le_bit
  154. ((unsigned long *)(bh->b_data), boundary, *beg);
  155. /*
  156. * search for a zero bit fails or the rest of bitmap block
  157. * cannot contain a zero window of minimum size
  158. */
  159. if (*beg + min > boundary) {
  160. brelse(bh);
  161. return 0;
  162. }
  163. if (unfm && is_block_in_journal(s, bmap_n, *beg, beg))
  164. continue;
  165. /* first zero bit found; we check next bits */
  166. for (end = *beg + 1;; end++) {
  167. if (end >= *beg + max || end >= boundary
  168. || reiserfs_test_le_bit(end, bh->b_data)) {
  169. next = end;
  170. break;
  171. }
  172. /*
  173. * finding the other end of zero bit window requires
  174. * looking into journal structures (in case of
  175. * searching for free blocks for unformatted nodes)
  176. */
  177. if (unfm && is_block_in_journal(s, bmap_n, end, &next))
  178. break;
  179. }
  180. /*
  181. * now (*beg) points to beginning of zero bits window,
  182. * (end) points to one bit after the window end
  183. */
  184. /* found window of proper size */
  185. if (end - *beg >= min) {
  186. int i;
  187. reiserfs_prepare_for_journal(s, bh, 1);
  188. /*
  189. * try to set all blocks used checking are
  190. * they still free
  191. */
  192. for (i = *beg; i < end; i++) {
  193. /* Don't check in journal again. */
  194. if (reiserfs_test_and_set_le_bit
  195. (i, bh->b_data)) {
  196. /*
  197. * bit was set by another process while
  198. * we slept in prepare_for_journal()
  199. */
  200. PROC_INFO_INC(s, scan_bitmap.stolen);
  201. /*
  202. * we can continue with smaller set
  203. * of allocated blocks, if length of
  204. * this set is more or equal to `min'
  205. */
  206. if (i >= *beg + min) {
  207. end = i;
  208. break;
  209. }
  210. /*
  211. * otherwise we clear all bit
  212. * were set ...
  213. */
  214. while (--i >= *beg)
  215. reiserfs_clear_le_bit
  216. (i, bh->b_data);
  217. reiserfs_restore_prepared_buffer(s, bh);
  218. *beg = org;
  219. /*
  220. * Search again in current block
  221. * from beginning
  222. */
  223. goto cont;
  224. }
  225. }
  226. bi->free_count -= (end - *beg);
  227. journal_mark_dirty(th, bh);
  228. brelse(bh);
  229. /* free block count calculation */
  230. reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s),
  231. 1);
  232. PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
  233. journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
  234. return end - (*beg);
  235. } else {
  236. *beg = next;
  237. }
  238. }
  239. }
  240. static int bmap_hash_id(struct super_block *s, u32 id)
  241. {
  242. char *hash_in = NULL;
  243. unsigned long hash;
  244. unsigned bm;
  245. if (id <= 2) {
  246. bm = 1;
  247. } else {
  248. hash_in = (char *)(&id);
  249. hash = keyed_hash(hash_in, 4);
  250. bm = hash % reiserfs_bmap_count(s);
  251. if (!bm)
  252. bm = 1;
  253. }
  254. /* this can only be true when SB_BMAP_NR = 1 */
  255. if (bm >= reiserfs_bmap_count(s))
  256. bm = 0;
  257. return bm;
  258. }
  259. /*
  260. * hashes the id and then returns > 0 if the block group for the
  261. * corresponding hash is full
  262. */
  263. static inline int block_group_used(struct super_block *s, u32 id)
  264. {
  265. int bm = bmap_hash_id(s, id);
  266. struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm];
  267. /*
  268. * If we don't have cached information on this bitmap block, we're
  269. * going to have to load it later anyway. Loading it here allows us
  270. * to make a better decision. This favors long-term performance gain
  271. * with a better on-disk layout vs. a short term gain of skipping the
  272. * read and potentially having a bad placement.
  273. */
  274. if (info->free_count == UINT_MAX) {
  275. struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm);
  276. brelse(bh);
  277. }
  278. if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) {
  279. return 0;
  280. }
  281. return 1;
  282. }
  283. /*
  284. * the packing is returned in disk byte order
  285. */
  286. __le32 reiserfs_choose_packing(struct inode * dir)
  287. {
  288. __le32 packing;
  289. if (TEST_OPTION(packing_groups, dir->i_sb)) {
  290. u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
  291. /*
  292. * some versions of reiserfsck expect packing locality 1 to be
  293. * special
  294. */
  295. if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir))
  296. packing = INODE_PKEY(dir)->k_objectid;
  297. else
  298. packing = INODE_PKEY(dir)->k_dir_id;
  299. } else
  300. packing = INODE_PKEY(dir)->k_objectid;
  301. return packing;
  302. }
  303. /*
  304. * Tries to find contiguous zero bit window (given size) in given region of
  305. * bitmap and place new blocks there. Returns number of allocated blocks.
  306. */
  307. static int scan_bitmap(struct reiserfs_transaction_handle *th,
  308. b_blocknr_t * start, b_blocknr_t finish,
  309. int min, int max, int unfm, sector_t file_block)
  310. {
  311. int nr_allocated = 0;
  312. struct super_block *s = th->t_super;
  313. unsigned int bm, off;
  314. unsigned int end_bm, end_off;
  315. unsigned int off_max = s->s_blocksize << 3;
  316. BUG_ON(!th->t_trans_id);
  317. PROC_INFO_INC(s, scan_bitmap.call);
  318. /* No point in looking for more free blocks */
  319. if (SB_FREE_BLOCKS(s) <= 0)
  320. return 0;
  321. get_bit_address(s, *start, &bm, &off);
  322. get_bit_address(s, finish, &end_bm, &end_off);
  323. if (bm > reiserfs_bmap_count(s))
  324. return 0;
  325. if (end_bm > reiserfs_bmap_count(s))
  326. end_bm = reiserfs_bmap_count(s);
  327. /*
  328. * When the bitmap is more than 10% free, anyone can allocate.
  329. * When it's less than 10% free, only files that already use the
  330. * bitmap are allowed. Once we pass 80% full, this restriction
  331. * is lifted.
  332. *
  333. * We do this so that files that grow later still have space close to
  334. * their original allocation. This improves locality, and presumably
  335. * performance as a result.
  336. *
  337. * This is only an allocation policy and does not make up for getting a
  338. * bad hint. Decent hinting must be implemented for this to work well.
  339. */
  340. if (TEST_OPTION(skip_busy, s)
  341. && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) {
  342. for (; bm < end_bm; bm++, off = 0) {
  343. if ((off && (!unfm || (file_block != 0)))
  344. || SB_AP_BITMAP(s)[bm].free_count >
  345. (s->s_blocksize << 3) / 10)
  346. nr_allocated =
  347. scan_bitmap_block(th, bm, &off, off_max,
  348. min, max, unfm);
  349. if (nr_allocated)
  350. goto ret;
  351. }
  352. /* we know from above that start is a reasonable number */
  353. get_bit_address(s, *start, &bm, &off);
  354. }
  355. for (; bm < end_bm; bm++, off = 0) {
  356. nr_allocated =
  357. scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
  358. if (nr_allocated)
  359. goto ret;
  360. }
  361. nr_allocated =
  362. scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
  363. ret:
  364. *start = bm * off_max + off;
  365. return nr_allocated;
  366. }
  367. static void _reiserfs_free_block(struct reiserfs_transaction_handle *th,
  368. struct inode *inode, b_blocknr_t block,
  369. int for_unformatted)
  370. {
  371. struct super_block *s = th->t_super;
  372. struct reiserfs_super_block *rs;
  373. struct buffer_head *sbh, *bmbh;
  374. struct reiserfs_bitmap_info *apbi;
  375. unsigned int nr, offset;
  376. BUG_ON(!th->t_trans_id);
  377. PROC_INFO_INC(s, free_block);
  378. rs = SB_DISK_SUPER_BLOCK(s);
  379. sbh = SB_BUFFER_WITH_SB(s);
  380. apbi = SB_AP_BITMAP(s);
  381. get_bit_address(s, block, &nr, &offset);
  382. if (nr >= reiserfs_bmap_count(s)) {
  383. reiserfs_error(s, "vs-4075", "block %lu is out of range",
  384. block);
  385. return;
  386. }
  387. bmbh = reiserfs_read_bitmap_block(s, nr);
  388. if (!bmbh)
  389. return;
  390. reiserfs_prepare_for_journal(s, bmbh, 1);
  391. /* clear bit for the given block in bit map */
  392. if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) {
  393. reiserfs_error(s, "vs-4080",
  394. "block %lu: bit already cleared", block);
  395. }
  396. apbi[nr].free_count++;
  397. journal_mark_dirty(th, bmbh);
  398. brelse(bmbh);
  399. reiserfs_prepare_for_journal(s, sbh, 1);
  400. /* update super block */
  401. set_sb_free_blocks(rs, sb_free_blocks(rs) + 1);
  402. journal_mark_dirty(th, sbh);
  403. if (for_unformatted) {
  404. int depth = reiserfs_write_unlock_nested(s);
  405. dquot_free_block_nodirty(inode, 1);
  406. reiserfs_write_lock_nested(s, depth);
  407. }
  408. }
  409. void reiserfs_free_block(struct reiserfs_transaction_handle *th,
  410. struct inode *inode, b_blocknr_t block,
  411. int for_unformatted)
  412. {
  413. struct super_block *s = th->t_super;
  414. BUG_ON(!th->t_trans_id);
  415. RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
  416. if (!is_reusable(s, block, 1))
  417. return;
  418. if (block > sb_block_count(REISERFS_SB(s)->s_rs)) {
  419. reiserfs_error(th->t_super, "bitmap-4072",
  420. "Trying to free block outside file system "
  421. "boundaries (%lu > %lu)",
  422. block, sb_block_count(REISERFS_SB(s)->s_rs));
  423. return;
  424. }
  425. /* mark it before we clear it, just in case */
  426. journal_mark_freed(th, s, block);
  427. _reiserfs_free_block(th, inode, block, for_unformatted);
  428. }
  429. /* preallocated blocks don't need to be run through journal_mark_freed */
  430. static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th,
  431. struct inode *inode, b_blocknr_t block)
  432. {
  433. BUG_ON(!th->t_trans_id);
  434. RFALSE(!th->t_super,
  435. "vs-4060: trying to free block on nonexistent device");
  436. if (!is_reusable(th->t_super, block, 1))
  437. return;
  438. _reiserfs_free_block(th, inode, block, 1);
  439. }
  440. static void __discard_prealloc(struct reiserfs_transaction_handle *th,
  441. struct reiserfs_inode_info *ei)
  442. {
  443. unsigned long save = ei->i_prealloc_block;
  444. int dirty = 0;
  445. struct inode *inode = &ei->vfs_inode;
  446. BUG_ON(!th->t_trans_id);
  447. #ifdef CONFIG_REISERFS_CHECK
  448. if (ei->i_prealloc_count < 0)
  449. reiserfs_error(th->t_super, "zam-4001",
  450. "inode has negative prealloc blocks count.");
  451. #endif
  452. while (ei->i_prealloc_count > 0) {
  453. b_blocknr_t block_to_free;
  454. /*
  455. * reiserfs_free_prealloc_block can drop the write lock,
  456. * which could allow another caller to free the same block.
  457. * We can protect against it by modifying the prealloc
  458. * state before calling it.
  459. */
  460. block_to_free = ei->i_prealloc_block++;
  461. ei->i_prealloc_count--;
  462. reiserfs_free_prealloc_block(th, inode, block_to_free);
  463. dirty = 1;
  464. }
  465. if (dirty)
  466. reiserfs_update_sd(th, inode);
  467. ei->i_prealloc_block = save;
  468. list_del_init(&ei->i_prealloc_list);
  469. }
  470. /* FIXME: It should be inline function */
  471. void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th,
  472. struct inode *inode)
  473. {
  474. struct reiserfs_inode_info *ei = REISERFS_I(inode);
  475. BUG_ON(!th->t_trans_id);
  476. if (ei->i_prealloc_count)
  477. __discard_prealloc(th, ei);
  478. }
  479. void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th)
  480. {
  481. struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
  482. BUG_ON(!th->t_trans_id);
  483. while (!list_empty(plist)) {
  484. struct reiserfs_inode_info *ei;
  485. ei = list_entry(plist->next, struct reiserfs_inode_info,
  486. i_prealloc_list);
  487. #ifdef CONFIG_REISERFS_CHECK
  488. if (!ei->i_prealloc_count) {
  489. reiserfs_error(th->t_super, "zam-4001",
  490. "inode is in prealloc list but has "
  491. "no preallocated blocks.");
  492. }
  493. #endif
  494. __discard_prealloc(th, ei);
  495. }
  496. }
  497. void reiserfs_init_alloc_options(struct super_block *s)
  498. {
  499. set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
  500. set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
  501. set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
  502. }
  503. /* block allocator related options are parsed here */
  504. int reiserfs_parse_alloc_options(struct super_block *s, char *options)
  505. {
  506. char *this_char, *value;
  507. /* clear default settings */
  508. REISERFS_SB(s)->s_alloc_options.bits = 0;
  509. while ((this_char = strsep(&options, ":")) != NULL) {
  510. if ((value = strchr(this_char, '=')) != NULL)
  511. *value++ = 0;
  512. if (!strcmp(this_char, "concentrating_formatted_nodes")) {
  513. int temp;
  514. SET_OPTION(concentrating_formatted_nodes);
  515. temp = (value
  516. && *value) ? simple_strtoul(value, &value,
  517. 0) : 10;
  518. if (temp <= 0 || temp > 100) {
  519. REISERFS_SB(s)->s_alloc_options.border = 10;
  520. } else {
  521. REISERFS_SB(s)->s_alloc_options.border =
  522. 100 / temp;
  523. }
  524. continue;
  525. }
  526. if (!strcmp(this_char, "displacing_large_files")) {
  527. SET_OPTION(displacing_large_files);
  528. REISERFS_SB(s)->s_alloc_options.large_file_size =
  529. (value
  530. && *value) ? simple_strtoul(value, &value, 0) : 16;
  531. continue;
  532. }
  533. if (!strcmp(this_char, "displacing_new_packing_localities")) {
  534. SET_OPTION(displacing_new_packing_localities);
  535. continue;
  536. }
  537. if (!strcmp(this_char, "old_hashed_relocation")) {
  538. SET_OPTION(old_hashed_relocation);
  539. continue;
  540. }
  541. if (!strcmp(this_char, "new_hashed_relocation")) {
  542. SET_OPTION(new_hashed_relocation);
  543. continue;
  544. }
  545. if (!strcmp(this_char, "dirid_groups")) {
  546. SET_OPTION(dirid_groups);
  547. continue;
  548. }
  549. if (!strcmp(this_char, "oid_groups")) {
  550. SET_OPTION(oid_groups);
  551. continue;
  552. }
  553. if (!strcmp(this_char, "packing_groups")) {
  554. SET_OPTION(packing_groups);
  555. continue;
  556. }
  557. if (!strcmp(this_char, "hashed_formatted_nodes")) {
  558. SET_OPTION(hashed_formatted_nodes);
  559. continue;
  560. }
  561. if (!strcmp(this_char, "skip_busy")) {
  562. SET_OPTION(skip_busy);
  563. continue;
  564. }
  565. if (!strcmp(this_char, "hundredth_slices")) {
  566. SET_OPTION(hundredth_slices);
  567. continue;
  568. }
  569. if (!strcmp(this_char, "old_way")) {
  570. SET_OPTION(old_way);
  571. continue;
  572. }
  573. if (!strcmp(this_char, "displace_based_on_dirid")) {
  574. SET_OPTION(displace_based_on_dirid);
  575. continue;
  576. }
  577. if (!strcmp(this_char, "preallocmin")) {
  578. REISERFS_SB(s)->s_alloc_options.preallocmin =
  579. (value
  580. && *value) ? simple_strtoul(value, &value, 0) : 4;
  581. continue;
  582. }
  583. if (!strcmp(this_char, "preallocsize")) {
  584. REISERFS_SB(s)->s_alloc_options.preallocsize =
  585. (value
  586. && *value) ? simple_strtoul(value, &value,
  587. 0) :
  588. PREALLOCATION_SIZE;
  589. continue;
  590. }
  591. reiserfs_warning(s, "zam-4001", "unknown option - %s",
  592. this_char);
  593. return 1;
  594. }
  595. reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
  596. return 0;
  597. }
  598. static void print_sep(struct seq_file *seq, int *first)
  599. {
  600. if (!*first)
  601. seq_puts(seq, ":");
  602. else
  603. *first = 0;
  604. }
  605. void show_alloc_options(struct seq_file *seq, struct super_block *s)
  606. {
  607. int first = 1;
  608. if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) |
  609. (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups)))
  610. return;
  611. seq_puts(seq, ",alloc=");
  612. if (TEST_OPTION(concentrating_formatted_nodes, s)) {
  613. print_sep(seq, &first);
  614. if (REISERFS_SB(s)->s_alloc_options.border != 10) {
  615. seq_printf(seq, "concentrating_formatted_nodes=%d",
  616. 100 / REISERFS_SB(s)->s_alloc_options.border);
  617. } else
  618. seq_puts(seq, "concentrating_formatted_nodes");
  619. }
  620. if (TEST_OPTION(displacing_large_files, s)) {
  621. print_sep(seq, &first);
  622. if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) {
  623. seq_printf(seq, "displacing_large_files=%lu",
  624. REISERFS_SB(s)->s_alloc_options.large_file_size);
  625. } else
  626. seq_puts(seq, "displacing_large_files");
  627. }
  628. if (TEST_OPTION(displacing_new_packing_localities, s)) {
  629. print_sep(seq, &first);
  630. seq_puts(seq, "displacing_new_packing_localities");
  631. }
  632. if (TEST_OPTION(old_hashed_relocation, s)) {
  633. print_sep(seq, &first);
  634. seq_puts(seq, "old_hashed_relocation");
  635. }
  636. if (TEST_OPTION(new_hashed_relocation, s)) {
  637. print_sep(seq, &first);
  638. seq_puts(seq, "new_hashed_relocation");
  639. }
  640. if (TEST_OPTION(dirid_groups, s)) {
  641. print_sep(seq, &first);
  642. seq_puts(seq, "dirid_groups");
  643. }
  644. if (TEST_OPTION(oid_groups, s)) {
  645. print_sep(seq, &first);
  646. seq_puts(seq, "oid_groups");
  647. }
  648. if (TEST_OPTION(packing_groups, s)) {
  649. print_sep(seq, &first);
  650. seq_puts(seq, "packing_groups");
  651. }
  652. if (TEST_OPTION(hashed_formatted_nodes, s)) {
  653. print_sep(seq, &first);
  654. seq_puts(seq, "hashed_formatted_nodes");
  655. }
  656. if (TEST_OPTION(skip_busy, s)) {
  657. print_sep(seq, &first);
  658. seq_puts(seq, "skip_busy");
  659. }
  660. if (TEST_OPTION(hundredth_slices, s)) {
  661. print_sep(seq, &first);
  662. seq_puts(seq, "hundredth_slices");
  663. }
  664. if (TEST_OPTION(old_way, s)) {
  665. print_sep(seq, &first);
  666. seq_puts(seq, "old_way");
  667. }
  668. if (TEST_OPTION(displace_based_on_dirid, s)) {
  669. print_sep(seq, &first);
  670. seq_puts(seq, "displace_based_on_dirid");
  671. }
  672. if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) {
  673. print_sep(seq, &first);
  674. seq_printf(seq, "preallocmin=%d",
  675. REISERFS_SB(s)->s_alloc_options.preallocmin);
  676. }
  677. if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) {
  678. print_sep(seq, &first);
  679. seq_printf(seq, "preallocsize=%d",
  680. REISERFS_SB(s)->s_alloc_options.preallocsize);
  681. }
  682. }
  683. static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint)
  684. {
  685. char *hash_in;
  686. if (hint->formatted_node) {
  687. hash_in = (char *)&hint->key.k_dir_id;
  688. } else {
  689. if (!hint->inode) {
  690. /*hint->search_start = hint->beg;*/
  691. hash_in = (char *)&hint->key.k_dir_id;
  692. } else
  693. if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
  694. hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
  695. else
  696. hash_in =
  697. (char *)(&INODE_PKEY(hint->inode)->k_objectid);
  698. }
  699. hint->search_start =
  700. hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
  701. }
  702. /*
  703. * Relocation based on dirid, hashing them into a given bitmap block
  704. * files. Formatted nodes are unaffected, a separate policy covers them
  705. */
  706. static void dirid_groups(reiserfs_blocknr_hint_t * hint)
  707. {
  708. unsigned long hash;
  709. __u32 dirid = 0;
  710. int bm = 0;
  711. struct super_block *sb = hint->th->t_super;
  712. if (hint->inode)
  713. dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
  714. else if (hint->formatted_node)
  715. dirid = hint->key.k_dir_id;
  716. if (dirid) {
  717. bm = bmap_hash_id(sb, dirid);
  718. hash = bm * (sb->s_blocksize << 3);
  719. /* give a portion of the block group to metadata */
  720. if (hint->inode)
  721. hash += sb->s_blocksize / 2;
  722. hint->search_start = hash;
  723. }
  724. }
  725. /*
  726. * Relocation based on oid, hashing them into a given bitmap block
  727. * files. Formatted nodes are unaffected, a separate policy covers them
  728. */
  729. static void oid_groups(reiserfs_blocknr_hint_t * hint)
  730. {
  731. if (hint->inode) {
  732. unsigned long hash;
  733. __u32 oid;
  734. __u32 dirid;
  735. int bm;
  736. dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
  737. /*
  738. * keep the root dir and it's first set of subdirs close to
  739. * the start of the disk
  740. */
  741. if (dirid <= 2)
  742. hash = (hint->inode->i_sb->s_blocksize << 3);
  743. else {
  744. oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
  745. bm = bmap_hash_id(hint->inode->i_sb, oid);
  746. hash = bm * (hint->inode->i_sb->s_blocksize << 3);
  747. }
  748. hint->search_start = hash;
  749. }
  750. }
  751. /*
  752. * returns 1 if it finds an indirect item and gets valid hint info
  753. * from it, otherwise 0
  754. */
  755. static int get_left_neighbor(reiserfs_blocknr_hint_t * hint)
  756. {
  757. struct treepath *path;
  758. struct buffer_head *bh;
  759. struct item_head *ih;
  760. int pos_in_item;
  761. __le32 *item;
  762. int ret = 0;
  763. /*
  764. * reiserfs code can call this function w/o pointer to path
  765. * structure supplied; then we rely on supplied search_start
  766. */
  767. if (!hint->path)
  768. return 0;
  769. path = hint->path;
  770. bh = get_last_bh(path);
  771. RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor");
  772. ih = tp_item_head(path);
  773. pos_in_item = path->pos_in_item;
  774. item = tp_item_body(path);
  775. hint->search_start = bh->b_blocknr;
  776. /*
  777. * for indirect item: go to left and look for the first non-hole entry
  778. * in the indirect item
  779. */
  780. if (!hint->formatted_node && is_indirect_le_ih(ih)) {
  781. if (pos_in_item == I_UNFM_NUM(ih))
  782. pos_in_item--;
  783. while (pos_in_item >= 0) {
  784. int t = get_block_num(item, pos_in_item);
  785. if (t) {
  786. hint->search_start = t;
  787. ret = 1;
  788. break;
  789. }
  790. pos_in_item--;
  791. }
  792. }
  793. /* does result value fit into specified region? */
  794. return ret;
  795. }
  796. /*
  797. * should be, if formatted node, then try to put on first part of the device
  798. * specified as number of percent with mount option device, else try to put
  799. * on last of device. This is not to say it is good code to do so,
  800. * but the effect should be measured.
  801. */
  802. static inline void set_border_in_hint(struct super_block *s,
  803. reiserfs_blocknr_hint_t * hint)
  804. {
  805. b_blocknr_t border =
  806. SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
  807. if (hint->formatted_node)
  808. hint->end = border - 1;
  809. else
  810. hint->beg = border;
  811. }
  812. static inline void displace_large_file(reiserfs_blocknr_hint_t * hint)
  813. {
  814. if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
  815. hint->search_start =
  816. hint->beg +
  817. keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id),
  818. 4) % (hint->end - hint->beg);
  819. else
  820. hint->search_start =
  821. hint->beg +
  822. keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid),
  823. 4) % (hint->end - hint->beg);
  824. }
  825. static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint)
  826. {
  827. char *hash_in;
  828. if (!hint->inode)
  829. hash_in = (char *)&hint->key.k_dir_id;
  830. else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
  831. hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
  832. else
  833. hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
  834. hint->search_start =
  835. hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
  836. }
  837. static inline int
  838. this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *
  839. hint)
  840. {
  841. return hint->block ==
  842. REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
  843. }
  844. #ifdef DISPLACE_NEW_PACKING_LOCALITIES
  845. static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint)
  846. {
  847. struct in_core_key *key = &hint->key;
  848. hint->th->displace_new_blocks = 0;
  849. hint->search_start =
  850. hint->beg + keyed_hash((char *)(&key->k_objectid),
  851. 4) % (hint->end - hint->beg);
  852. }
  853. #endif
  854. static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint)
  855. {
  856. b_blocknr_t border;
  857. u32 hash_in;
  858. if (hint->formatted_node || hint->inode == NULL) {
  859. return 0;
  860. }
  861. hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
  862. border =
  863. hint->beg + (u32) keyed_hash(((char *)(&hash_in)),
  864. 4) % (hint->end - hint->beg - 1);
  865. if (border > hint->search_start)
  866. hint->search_start = border;
  867. return 1;
  868. }
  869. static inline int old_way(reiserfs_blocknr_hint_t * hint)
  870. {
  871. b_blocknr_t border;
  872. if (hint->formatted_node || hint->inode == NULL) {
  873. return 0;
  874. }
  875. border =
  876. hint->beg +
  877. le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end -
  878. hint->beg);
  879. if (border > hint->search_start)
  880. hint->search_start = border;
  881. return 1;
  882. }
  883. static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint)
  884. {
  885. struct in_core_key *key = &hint->key;
  886. b_blocknr_t slice_start;
  887. slice_start =
  888. (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100);
  889. if (slice_start > hint->search_start
  890. || slice_start + (hint->end / 100) <= hint->search_start) {
  891. hint->search_start = slice_start;
  892. }
  893. }
  894. static void determine_search_start(reiserfs_blocknr_hint_t * hint,
  895. int amount_needed)
  896. {
  897. struct super_block *s = hint->th->t_super;
  898. int unfm_hint;
  899. hint->beg = 0;
  900. hint->end = SB_BLOCK_COUNT(s) - 1;
  901. /* This is former border algorithm. Now with tunable border offset */
  902. if (concentrating_formatted_nodes(s))
  903. set_border_in_hint(s, hint);
  904. #ifdef DISPLACE_NEW_PACKING_LOCALITIES
  905. /*
  906. * whenever we create a new directory, we displace it. At first
  907. * we will hash for location, later we might look for a moderately
  908. * empty place for it
  909. */
  910. if (displacing_new_packing_localities(s)
  911. && hint->th->displace_new_blocks) {
  912. displace_new_packing_locality(hint);
  913. /*
  914. * we do not continue determine_search_start,
  915. * if new packing locality is being displaced
  916. */
  917. return;
  918. }
  919. #endif
  920. /*
  921. * all persons should feel encouraged to add more special cases
  922. * here and test them
  923. */
  924. if (displacing_large_files(s) && !hint->formatted_node
  925. && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
  926. displace_large_file(hint);
  927. return;
  928. }
  929. /*
  930. * if none of our special cases is relevant, use the left
  931. * neighbor in the tree order of the new node we are allocating for
  932. */
  933. if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) {
  934. hash_formatted_node(hint);
  935. return;
  936. }
  937. unfm_hint = get_left_neighbor(hint);
  938. /*
  939. * Mimic old block allocator behaviour, that is if VFS allowed for
  940. * preallocation, new blocks are displaced based on directory ID.
  941. * Also, if suggested search_start is less than last preallocated
  942. * block, we start searching from it, assuming that HDD dataflow
  943. * is faster in forward direction
  944. */
  945. if (TEST_OPTION(old_way, s)) {
  946. if (!hint->formatted_node) {
  947. if (!reiserfs_hashed_relocation(s))
  948. old_way(hint);
  949. else if (!reiserfs_no_unhashed_relocation(s))
  950. old_hashed_relocation(hint);
  951. if (hint->inode
  952. && hint->search_start <
  953. REISERFS_I(hint->inode)->i_prealloc_block)
  954. hint->search_start =
  955. REISERFS_I(hint->inode)->i_prealloc_block;
  956. }
  957. return;
  958. }
  959. /* This is an approach proposed by Hans */
  960. if (TEST_OPTION(hundredth_slices, s)
  961. && !(displacing_large_files(s) && !hint->formatted_node)) {
  962. hundredth_slices(hint);
  963. return;
  964. }
  965. /* old_hashed_relocation only works on unformatted */
  966. if (!unfm_hint && !hint->formatted_node &&
  967. TEST_OPTION(old_hashed_relocation, s)) {
  968. old_hashed_relocation(hint);
  969. }
  970. /* new_hashed_relocation works with both formatted/unformatted nodes */
  971. if ((!unfm_hint || hint->formatted_node) &&
  972. TEST_OPTION(new_hashed_relocation, s)) {
  973. new_hashed_relocation(hint);
  974. }
  975. /* dirid grouping works only on unformatted nodes */
  976. if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
  977. dirid_groups(hint);
  978. }
  979. #ifdef DISPLACE_NEW_PACKING_LOCALITIES
  980. if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
  981. dirid_groups(hint);
  982. }
  983. #endif
  984. /* oid grouping works only on unformatted nodes */
  985. if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) {
  986. oid_groups(hint);
  987. }
  988. return;
  989. }
  990. static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
  991. {
  992. /* make minimum size a mount option and benchmark both ways */
  993. /* we preallocate blocks only for regular files, specific size */
  994. /* benchmark preallocating always and see what happens */
  995. hint->prealloc_size = 0;
  996. if (!hint->formatted_node && hint->preallocate) {
  997. if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode)
  998. && hint->inode->i_size >=
  999. REISERFS_SB(hint->th->t_super)->s_alloc_options.
  1000. preallocmin * hint->inode->i_sb->s_blocksize)
  1001. hint->prealloc_size =
  1002. REISERFS_SB(hint->th->t_super)->s_alloc_options.
  1003. preallocsize - 1;
  1004. }
  1005. return CARRY_ON;
  1006. }
  1007. static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint,
  1008. b_blocknr_t * new_blocknrs,
  1009. b_blocknr_t start,
  1010. b_blocknr_t finish, int min,
  1011. int amount_needed,
  1012. int prealloc_size)
  1013. {
  1014. int rest = amount_needed;
  1015. int nr_allocated;
  1016. while (rest > 0 && start <= finish) {
  1017. nr_allocated = scan_bitmap(hint->th, &start, finish, min,
  1018. rest + prealloc_size,
  1019. !hint->formatted_node, hint->block);
  1020. if (nr_allocated == 0) /* no new blocks allocated, return */
  1021. break;
  1022. /* fill free_blocknrs array first */
  1023. while (rest > 0 && nr_allocated > 0) {
  1024. *new_blocknrs++ = start++;
  1025. rest--;
  1026. nr_allocated--;
  1027. }
  1028. /* do we have something to fill prealloc. array also ? */
  1029. if (nr_allocated > 0) {
  1030. /*
  1031. * it means prealloc_size was greater that 0 and
  1032. * we do preallocation
  1033. */
  1034. list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
  1035. &SB_JOURNAL(hint->th->t_super)->
  1036. j_prealloc_list);
  1037. REISERFS_I(hint->inode)->i_prealloc_block = start;
  1038. REISERFS_I(hint->inode)->i_prealloc_count =
  1039. nr_allocated;
  1040. break;
  1041. }
  1042. }
  1043. return (amount_needed - rest);
  1044. }
  1045. static inline int blocknrs_and_prealloc_arrays_from_search_start
  1046. (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs,
  1047. int amount_needed) {
  1048. struct super_block *s = hint->th->t_super;
  1049. b_blocknr_t start = hint->search_start;
  1050. b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
  1051. int passno = 0;
  1052. int nr_allocated = 0;
  1053. int depth;
  1054. determine_prealloc_size(hint);
  1055. if (!hint->formatted_node) {
  1056. int quota_ret;
  1057. #ifdef REISERQUOTA_DEBUG
  1058. reiserfs_debug(s, REISERFS_DEBUG_CODE,
  1059. "reiserquota: allocating %d blocks id=%u",
  1060. amount_needed, hint->inode->i_uid);
  1061. #endif
  1062. depth = reiserfs_write_unlock_nested(s);
  1063. quota_ret =
  1064. dquot_alloc_block_nodirty(hint->inode, amount_needed);
  1065. if (quota_ret) { /* Quota exceeded? */
  1066. reiserfs_write_lock_nested(s, depth);
  1067. return QUOTA_EXCEEDED;
  1068. }
  1069. if (hint->preallocate && hint->prealloc_size) {
  1070. #ifdef REISERQUOTA_DEBUG
  1071. reiserfs_debug(s, REISERFS_DEBUG_CODE,
  1072. "reiserquota: allocating (prealloc) %d blocks id=%u",
  1073. hint->prealloc_size, hint->inode->i_uid);
  1074. #endif
  1075. quota_ret = dquot_prealloc_block_nodirty(hint->inode,
  1076. hint->prealloc_size);
  1077. if (quota_ret)
  1078. hint->preallocate = hint->prealloc_size = 0;
  1079. }
  1080. /* for unformatted nodes, force large allocations */
  1081. reiserfs_write_lock_nested(s, depth);
  1082. }
  1083. do {
  1084. switch (passno++) {
  1085. case 0: /* Search from hint->search_start to end of disk */
  1086. start = hint->search_start;
  1087. finish = SB_BLOCK_COUNT(s) - 1;
  1088. break;
  1089. case 1: /* Search from hint->beg to hint->search_start */
  1090. start = hint->beg;
  1091. finish = hint->search_start;
  1092. break;
  1093. case 2: /* Last chance: Search from 0 to hint->beg */
  1094. start = 0;
  1095. finish = hint->beg;
  1096. break;
  1097. default:
  1098. /* We've tried searching everywhere, not enough space */
  1099. /* Free the blocks */
  1100. if (!hint->formatted_node) {
  1101. #ifdef REISERQUOTA_DEBUG
  1102. reiserfs_debug(s, REISERFS_DEBUG_CODE,
  1103. "reiserquota: freeing (nospace) %d blocks id=%u",
  1104. amount_needed +
  1105. hint->prealloc_size -
  1106. nr_allocated,
  1107. hint->inode->i_uid);
  1108. #endif
  1109. /* Free not allocated blocks */
  1110. depth = reiserfs_write_unlock_nested(s);
  1111. dquot_free_block_nodirty(hint->inode,
  1112. amount_needed + hint->prealloc_size -
  1113. nr_allocated);
  1114. reiserfs_write_lock_nested(s, depth);
  1115. }
  1116. while (nr_allocated--)
  1117. reiserfs_free_block(hint->th, hint->inode,
  1118. new_blocknrs[nr_allocated],
  1119. !hint->formatted_node);
  1120. return NO_DISK_SPACE;
  1121. }
  1122. } while ((nr_allocated += allocate_without_wrapping_disk(hint,
  1123. new_blocknrs +
  1124. nr_allocated,
  1125. start, finish,
  1126. 1,
  1127. amount_needed -
  1128. nr_allocated,
  1129. hint->
  1130. prealloc_size))
  1131. < amount_needed);
  1132. if (!hint->formatted_node &&
  1133. amount_needed + hint->prealloc_size >
  1134. nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
  1135. /* Some of preallocation blocks were not allocated */
  1136. #ifdef REISERQUOTA_DEBUG
  1137. reiserfs_debug(s, REISERFS_DEBUG_CODE,
  1138. "reiserquota: freeing (failed prealloc) %d blocks id=%u",
  1139. amount_needed + hint->prealloc_size -
  1140. nr_allocated -
  1141. REISERFS_I(hint->inode)->i_prealloc_count,
  1142. hint->inode->i_uid);
  1143. #endif
  1144. depth = reiserfs_write_unlock_nested(s);
  1145. dquot_free_block_nodirty(hint->inode, amount_needed +
  1146. hint->prealloc_size - nr_allocated -
  1147. REISERFS_I(hint->inode)->
  1148. i_prealloc_count);
  1149. reiserfs_write_lock_nested(s, depth);
  1150. }
  1151. return CARRY_ON;
  1152. }
  1153. /* grab new blocknrs from preallocated list */
  1154. /* return amount still needed after using them */
  1155. static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint,
  1156. b_blocknr_t * new_blocknrs,
  1157. int amount_needed)
  1158. {
  1159. struct inode *inode = hint->inode;
  1160. if (REISERFS_I(inode)->i_prealloc_count > 0) {
  1161. while (amount_needed) {
  1162. *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++;
  1163. REISERFS_I(inode)->i_prealloc_count--;
  1164. amount_needed--;
  1165. if (REISERFS_I(inode)->i_prealloc_count <= 0) {
  1166. list_del(&REISERFS_I(inode)->i_prealloc_list);
  1167. break;
  1168. }
  1169. }
  1170. }
  1171. /* return amount still needed after using preallocated blocks */
  1172. return amount_needed;
  1173. }
  1174. int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
  1175. b_blocknr_t *new_blocknrs,
  1176. int amount_needed,
  1177. /* Amount of blocks we have already reserved */
  1178. int reserved_by_us)
  1179. {
  1180. int initial_amount_needed = amount_needed;
  1181. int ret;
  1182. struct super_block *s = hint->th->t_super;
  1183. /* Check if there is enough space, taking into account reserved space */
  1184. if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks <
  1185. amount_needed - reserved_by_us)
  1186. return NO_DISK_SPACE;
  1187. /* should this be if !hint->inode && hint->preallocate? */
  1188. /* do you mean hint->formatted_node can be removed ? - Zam */
  1189. /*
  1190. * hint->formatted_node cannot be removed because we try to access
  1191. * inode information here, and there is often no inode associated with
  1192. * metadata allocations - green
  1193. */
  1194. if (!hint->formatted_node && hint->preallocate) {
  1195. amount_needed = use_preallocated_list_if_available
  1196. (hint, new_blocknrs, amount_needed);
  1197. /*
  1198. * We have all the block numbers we need from the
  1199. * prealloc list
  1200. */
  1201. if (amount_needed == 0)
  1202. return CARRY_ON;
  1203. new_blocknrs += (initial_amount_needed - amount_needed);
  1204. }
  1205. /* find search start and save it in hint structure */
  1206. determine_search_start(hint, amount_needed);
  1207. if (hint->search_start >= SB_BLOCK_COUNT(s))
  1208. hint->search_start = SB_BLOCK_COUNT(s) - 1;
  1209. /* allocation itself; fill new_blocknrs and preallocation arrays */
  1210. ret = blocknrs_and_prealloc_arrays_from_search_start
  1211. (hint, new_blocknrs, amount_needed);
  1212. /*
  1213. * We used prealloc. list to fill (partially) new_blocknrs array.
  1214. * If final allocation fails we need to return blocks back to
  1215. * prealloc. list or just free them. -- Zam (I chose second
  1216. * variant)
  1217. */
  1218. if (ret != CARRY_ON) {
  1219. while (amount_needed++ < initial_amount_needed) {
  1220. reiserfs_free_block(hint->th, hint->inode,
  1221. *(--new_blocknrs), 1);
  1222. }
  1223. }
  1224. return ret;
  1225. }
  1226. void reiserfs_cache_bitmap_metadata(struct super_block *sb,
  1227. struct buffer_head *bh,
  1228. struct reiserfs_bitmap_info *info)
  1229. {
  1230. unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size);
  1231. /* The first bit must ALWAYS be 1 */
  1232. if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data))
  1233. reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is "
  1234. "corrupted: first bit must be 1", bh->b_blocknr);
  1235. info->free_count = 0;
  1236. while (--cur >= (unsigned long *)bh->b_data) {
  1237. /* 0 and ~0 are special, we can optimize for them */
  1238. if (*cur == 0)
  1239. info->free_count += BITS_PER_LONG;
  1240. else if (*cur != ~0L) /* A mix, investigate */
  1241. info->free_count += BITS_PER_LONG - hweight_long(*cur);
  1242. }
  1243. }
  1244. struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb,
  1245. unsigned int bitmap)
  1246. {
  1247. b_blocknr_t block = (sb->s_blocksize << 3) * bitmap;
  1248. struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap;
  1249. struct buffer_head *bh;
  1250. /*
  1251. * Way old format filesystems had the bitmaps packed up front.
  1252. * I doubt there are any of these left, but just in case...
  1253. */
  1254. if (unlikely(test_bit(REISERFS_OLD_FORMAT,
  1255. &REISERFS_SB(sb)->s_properties)))
  1256. block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap;
  1257. else if (bitmap == 0)
  1258. block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1;
  1259. bh = sb_bread(sb, block);
  1260. if (bh == NULL)
  1261. reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) "
  1262. "reading failed", __func__, block);
  1263. else {
  1264. if (buffer_locked(bh)) {
  1265. int depth;
  1266. PROC_INFO_INC(sb, scan_bitmap.wait);
  1267. depth = reiserfs_write_unlock_nested(sb);
  1268. __wait_on_buffer(bh);
  1269. reiserfs_write_lock_nested(sb, depth);
  1270. }
  1271. BUG_ON(!buffer_uptodate(bh));
  1272. BUG_ON(atomic_read(&bh->b_count) == 0);
  1273. if (info->free_count == UINT_MAX)
  1274. reiserfs_cache_bitmap_metadata(sb, bh, info);
  1275. }
  1276. return bh;
  1277. }
  1278. int reiserfs_init_bitmap_cache(struct super_block *sb)
  1279. {
  1280. struct reiserfs_bitmap_info *bitmap;
  1281. unsigned int bmap_nr = reiserfs_bmap_count(sb);
  1282. bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap)));
  1283. if (bitmap == NULL)
  1284. return -ENOMEM;
  1285. memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr);
  1286. SB_AP_BITMAP(sb) = bitmap;
  1287. return 0;
  1288. }
  1289. void reiserfs_free_bitmap_cache(struct super_block *sb)
  1290. {
  1291. if (SB_AP_BITMAP(sb)) {
  1292. vfree(SB_AP_BITMAP(sb));
  1293. SB_AP_BITMAP(sb) = NULL;
  1294. }
  1295. }