~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/reiserfs/bitmap.c

Version: ~ [ linux-5.4-rc7 ] ~ [ linux-5.3.11 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.84 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.154 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.201 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.201 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.77 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp