2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
4 /* Reiserfs block (de)allocator, bitmap-based. */
6 #include <linux/config.h>
7 #include <linux/time.h>
8 #include <linux/reiserfs_fs.h>
9 #include <linux/errno.h>
10 #include <linux/buffer_head.h>
11 #include <linux/kernel.h>
12 #include <linux/pagemap.h>
13 #include <linux/reiserfs_fs_sb.h>
14 #include <linux/reiserfs_fs_i.h>
15 #include <linux/quotaops.h>
17 #define PREALLOCATION_SIZE 9
19 /* different reiserfs block allocator options */
21 #define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
23 #define _ALLOC_concentrating_formatted_nodes 0
24 #define _ALLOC_displacing_large_files 1
25 #define _ALLOC_displacing_new_packing_localities 2
26 #define _ALLOC_old_hashed_relocation 3
27 #define _ALLOC_new_hashed_relocation 4
28 #define _ALLOC_skip_busy 5
29 #define _ALLOC_displace_based_on_dirid 6
30 #define _ALLOC_hashed_formatted_nodes 7
31 #define _ALLOC_old_way 8
32 #define _ALLOC_hundredth_slices 9
34 #define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
35 #define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
36 #define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
38 #define SET_OPTION(optname) \
40 reiserfs_warning(s, "reiserfs: option \"%s\" is set", #optname); \
41 set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
43 #define TEST_OPTION(optname, s) \
44 test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
46 static inline void get_bit_address (struct super_block * s,
47 b_blocknr_t block, int * bmap_nr, int * offset)
49 /* It is in the bitmap block number equal to the block
50 * number divided by the number of bits in a block. */
51 *bmap_nr = block / (s->s_blocksize << 3);
52 /* Within that bitmap block it is located at bit offset *offset. */
53 *offset = block & ((s->s_blocksize << 3) - 1 );
57 #ifdef CONFIG_REISERFS_CHECK
58 int is_reusable (struct super_block * s, b_blocknr_t block, int bit_value)
62 if (block == 0 || block >= SB_BLOCK_COUNT (s)) {
63 reiserfs_warning (s, "vs-4010: is_reusable: block number is out of range %lu (%u)",
64 block, SB_BLOCK_COUNT (s));
68 /* it can't be one of the bitmap blocks */
69 for (i = 0; i < SB_BMAP_NR (s); i ++)
70 if (block == SB_AP_BITMAP (s)[i].bh->b_blocknr) {
71 reiserfs_warning (s, "vs: 4020: is_reusable: "
72 "bitmap block %lu(%u) can't be freed or reused",
73 block, SB_BMAP_NR (s));
77 get_bit_address (s, block, &i, &j);
79 if (i >= SB_BMAP_NR (s)) {
80 reiserfs_warning (s, "vs-4030: is_reusable: there is no so many bitmap blocks: "
81 "block=%lu, bitmap_nr=%d", block, i);
85 if ((bit_value == 0 &&
86 reiserfs_test_le_bit(j, SB_AP_BITMAP(s)[i].bh->b_data)) ||
88 reiserfs_test_le_bit(j, SB_AP_BITMAP (s)[i].bh->b_data) == 0)) {
89 reiserfs_warning (s, "vs-4040: is_reusable: corresponding bit of block %lu does not "
90 "match required value (i==%d, j==%d) test_bit==%d",
91 block, i, j, reiserfs_test_le_bit (j, SB_AP_BITMAP (s)[i].bh->b_data));
96 if (bit_value == 0 && block == SB_ROOT_BLOCK (s)) {
97 reiserfs_warning (s, "vs-4050: is_reusable: this is root block (%u), "
98 "it must be busy", SB_ROOT_BLOCK (s));
104 #endif /* CONFIG_REISERFS_CHECK */
106 /* searches in journal structures for a given block number (bmap, off). If block
107 is found in reiserfs journal it suggests next free block candidate to test. */
108 static inline int is_block_in_journal (struct super_block * s, int bmap, int
113 if (reiserfs_in_journal (s, bmap, off, 1, &tmp)) {
114 if (tmp) { /* hint supplied */
116 PROC_INFO_INC( s, scan_bitmap.in_journal_hint );
118 (*next) = off + 1; /* inc offset to avoid looping. */
119 PROC_INFO_INC( s, scan_bitmap.in_journal_nohint );
121 PROC_INFO_INC( s, scan_bitmap.retry );
127 /* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
129 static int scan_bitmap_block (struct reiserfs_transaction_handle *th,
130 int bmap_n, int *beg, int boundary, int min, int max, int unfm)
132 struct super_block *s = th->t_super;
133 struct reiserfs_bitmap_info *bi=&SB_AP_BITMAP(s)[bmap_n];
137 RFALSE(bmap_n >= SB_BMAP_NR (s), "Bitmap %d is out of range (0..%d)",bmap_n, SB_BMAP_NR (s) - 1);
138 PROC_INFO_INC( s, scan_bitmap.bmap );
139 /* this is unclear and lacks comments, explain how journal bitmaps
140 work here for the reader. Convey a sense of the design here. What
142 /* - I mean `a window of zero bits' as in description of this function - Zam. */
145 reiserfs_warning (s, "NULL bitmap info pointer for bitmap %d", bmap_n);
148 if (buffer_locked (bi->bh)) {
149 PROC_INFO_INC( s, scan_bitmap.wait );
150 __wait_on_buffer (bi->bh);
153 /* If we know that first zero bit is only one or first zero bit is
154 closer to the end of bitmap than our start pointer */
155 if (bi->first_zero_hint > *beg || bi->free_count == 1)
156 *beg = bi->first_zero_hint;
160 if (bi->free_count < min)
161 return 0; // No free blocks in this bitmap
163 /* search for a first zero bit -- beggining of a window */
164 *beg = reiserfs_find_next_zero_le_bit
165 ((unsigned long*)(bi->bh->b_data), boundary, *beg);
167 if (*beg + min > boundary) { /* search for a zero bit fails or the rest of bitmap block
168 * cannot contain a zero window of minimum size */
172 if (unfm && is_block_in_journal(s,bmap_n, *beg, beg))
174 /* first zero bit found; we check next bits */
175 for (end = *beg + 1;; end ++) {
176 if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit (end, bi->bh->b_data)) {
180 /* finding the other end of zero bit window requires looking into journal structures (in
181 * case of searching for free blocks for unformatted nodes) */
182 if (unfm && is_block_in_journal(s, bmap_n, end, &next))
186 /* now (*beg) points to beginning of zero bits window,
187 * (end) points to one bit after the window end */
188 if (end - *beg >= min) { /* it seems we have found window of proper size */
190 reiserfs_prepare_for_journal (s, bi->bh, 1);
191 /* try to set all blocks used checking are they still free */
192 for (i = *beg; i < end; i++) {
193 /* It seems that we should not check in journal again. */
194 if (reiserfs_test_and_set_le_bit (i, bi->bh->b_data)) {
195 /* bit was set by another process
196 * while we slept in prepare_for_journal() */
197 PROC_INFO_INC( s, scan_bitmap.stolen );
198 if (i >= *beg + min) { /* we can continue with smaller set of allocated blocks,
199 * if length of this set is more or equal to `min' */
203 /* otherwise we clear all bit were set ... */
205 reiserfs_test_and_clear_le_bit (i, bi->bh->b_data);
206 reiserfs_restore_prepared_buffer (s, bi->bh);
207 *beg = max(org, (int)bi->first_zero_hint);
208 /* ... and search again in current block from beginning */
212 bi->free_count -= (end - *beg);
214 /* if search started from zero_hint bit, and zero hint have not
215 changed since, then we need to update first_zero_hint */
216 if ( bi->first_zero_hint >= *beg)
217 /* no point in looking for free bit if there is not any */
218 bi->first_zero_hint = (bi->free_count > 0 ) ?
219 reiserfs_find_next_zero_le_bit
220 ((unsigned long*)(bi->bh->b_data), s->s_blocksize << 3, end) : (s->s_blocksize << 3);
222 journal_mark_dirty (th, s, bi->bh);
224 /* free block count calculation */
225 reiserfs_prepare_for_journal (s, SB_BUFFER_WITH_SB(s), 1);
226 PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
227 journal_mark_dirty (th, s, SB_BUFFER_WITH_SB(s));
236 /* Tries to find contiguous zero bit window (given size) in given region of
237 * bitmap and place new blocks there. Returns number of allocated blocks. */
238 static int scan_bitmap (struct reiserfs_transaction_handle *th,
239 b_blocknr_t *start, b_blocknr_t finish,
240 int min, int max, int unfm, unsigned long file_block)
243 struct super_block * s = th->t_super;
244 /* find every bm and bmap and bmap_nr in this file, and change them all to bitmap_blocknr
245 * - Hans, it is not a block number - Zam. */
249 int off_max = s->s_blocksize << 3;
251 PROC_INFO_INC( s, scan_bitmap.call );
252 if ( SB_FREE_BLOCKS(s) <= 0)
253 return 0; // No point in looking for more free blocks
255 get_bit_address (s, *start, &bm, &off);
256 get_bit_address (s, finish, &end_bm, &end_off);
258 // With this option set first we try to find a bitmap that is at least 10%
259 // free, and if that fails, then we fall back to old whole bitmap scanning
260 if ( TEST_OPTION(skip_busy, s) && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s)/20 ) {
261 for (;bm < end_bm; bm++, off = 0) {
262 if ( ( off && (!unfm || (file_block != 0))) || SB_AP_BITMAP(s)[bm].free_count > (s->s_blocksize << 3) / 10 )
263 nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
267 get_bit_address (s, *start, &bm, &off);
270 for (;bm < end_bm; bm++, off = 0) {
271 nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
276 nr_allocated = scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
279 *start = bm * off_max + off;
284 static void _reiserfs_free_block (struct reiserfs_transaction_handle *th,
285 struct inode *inode, b_blocknr_t block,
288 struct super_block * s = th->t_super;
289 struct reiserfs_super_block * rs;
290 struct buffer_head * sbh;
291 struct reiserfs_bitmap_info *apbi;
294 PROC_INFO_INC( s, free_block );
296 rs = SB_DISK_SUPER_BLOCK (s);
297 sbh = SB_BUFFER_WITH_SB (s);
298 apbi = SB_AP_BITMAP(s);
300 get_bit_address (s, block, &nr, &offset);
302 if (nr >= sb_bmap_nr (rs)) {
303 reiserfs_warning (s, "vs-4075: reiserfs_free_block: "
304 "block %lu is out of range on %s",
305 block, reiserfs_bdevname (s));
309 reiserfs_prepare_for_journal(s, apbi[nr].bh, 1 ) ;
311 /* clear bit for the given block in bit map */
312 if (!reiserfs_test_and_clear_le_bit (offset, apbi[nr].bh->b_data)) {
313 reiserfs_warning (s, "vs-4080: reiserfs_free_block: "
314 "free_block (%s:%lu)[dev:blocknr]: bit already cleared",
315 reiserfs_bdevname (s), block);
317 if (offset < apbi[nr].first_zero_hint) {
318 apbi[nr].first_zero_hint = offset;
320 apbi[nr].free_count ++;
321 journal_mark_dirty (th, s, apbi[nr].bh);
323 reiserfs_prepare_for_journal(s, sbh, 1) ;
324 /* update super block */
325 set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );
327 journal_mark_dirty (th, s, sbh);
329 DQUOT_FREE_BLOCK_NODIRTY(inode, 1);
332 void reiserfs_free_block (struct reiserfs_transaction_handle *th,
333 struct inode *inode, b_blocknr_t block,
336 struct super_block * s = th->t_super;
338 RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
339 RFALSE(is_reusable (s, block, 1) == 0, "vs-4071: can not free such block");
340 /* mark it before we clear it, just in case */
341 journal_mark_freed(th, s, block) ;
342 _reiserfs_free_block(th, inode, block, for_unformatted) ;
345 /* preallocated blocks don't need to be run through journal_mark_freed */
346 void reiserfs_free_prealloc_block (struct reiserfs_transaction_handle *th,
347 struct inode *inode, b_blocknr_t block) {
348 RFALSE(!th->t_super, "vs-4060: trying to free block on nonexistent device");
349 RFALSE(is_reusable (th->t_super, block, 1) == 0, "vs-4070: can not free such block");
350 _reiserfs_free_block(th, inode, block, 1) ;
353 static void __discard_prealloc (struct reiserfs_transaction_handle * th,
354 struct reiserfs_inode_info *ei)
356 unsigned long save = ei->i_prealloc_block ;
358 struct inode *inode = &ei->vfs_inode;
359 #ifdef CONFIG_REISERFS_CHECK
360 if (ei->i_prealloc_count < 0)
361 reiserfs_warning (th->t_super, "zam-4001:%s: inode has negative prealloc blocks count.", __FUNCTION__ );
363 while (ei->i_prealloc_count > 0) {
364 reiserfs_free_prealloc_block(th, inode, ei->i_prealloc_block);
365 ei->i_prealloc_block++;
366 ei->i_prealloc_count --;
370 reiserfs_update_sd(th, inode);
371 ei->i_prealloc_block = save;
372 list_del_init(&(ei->i_prealloc_list));
375 /* FIXME: It should be inline function */
376 void reiserfs_discard_prealloc (struct reiserfs_transaction_handle *th,
379 struct reiserfs_inode_info *ei = REISERFS_I(inode);
380 if (ei->i_prealloc_count)
381 __discard_prealloc(th, ei);
384 void reiserfs_discard_all_prealloc (struct reiserfs_transaction_handle *th)
386 struct list_head * plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
388 while (!list_empty(plist)) {
389 struct reiserfs_inode_info *ei;
390 ei = list_entry(plist->next, struct reiserfs_inode_info, i_prealloc_list);
391 #ifdef CONFIG_REISERFS_CHECK
392 if (!ei->i_prealloc_count) {
393 reiserfs_warning (th->t_super, "zam-4001:%s: inode is in prealloc list but has no preallocated blocks.", __FUNCTION__);
396 __discard_prealloc(th, ei);
399 /* block allocator related options are parsed here */
400 int reiserfs_parse_alloc_options(struct super_block * s, char * options)
402 char * this_char, * value;
404 REISERFS_SB(s)->s_alloc_options.bits = 0; /* clear default settings */
406 while ( (this_char = strsep (&options, ":")) != NULL ) {
407 if ((value = strchr (this_char, '=')) != NULL)
410 if (!strcmp(this_char, "concentrating_formatted_nodes")) {
412 SET_OPTION(concentrating_formatted_nodes);
413 temp = (value && *value) ? simple_strtoul (value, &value, 0) : 10;
414 if (temp <= 0 || temp > 100) {
415 REISERFS_SB(s)->s_alloc_options.border = 10;
417 REISERFS_SB(s)->s_alloc_options.border = 100 / temp;
421 if (!strcmp(this_char, "displacing_large_files")) {
422 SET_OPTION(displacing_large_files);
423 REISERFS_SB(s)->s_alloc_options.large_file_size =
424 (value && *value) ? simple_strtoul (value, &value, 0) : 16;
427 if (!strcmp(this_char, "displacing_new_packing_localities")) {
428 SET_OPTION(displacing_new_packing_localities);
432 if (!strcmp(this_char, "old_hashed_relocation")) {
433 SET_OPTION(old_hashed_relocation);
437 if (!strcmp(this_char, "new_hashed_relocation")) {
438 SET_OPTION(new_hashed_relocation);
442 if (!strcmp(this_char, "hashed_formatted_nodes")) {
443 SET_OPTION(hashed_formatted_nodes);
447 if (!strcmp(this_char, "skip_busy")) {
448 SET_OPTION(skip_busy);
452 if (!strcmp(this_char, "hundredth_slices")) {
453 SET_OPTION(hundredth_slices);
457 if (!strcmp(this_char, "old_way")) {
462 if (!strcmp(this_char, "displace_based_on_dirid")) {
463 SET_OPTION(displace_based_on_dirid);
467 if (!strcmp(this_char, "preallocmin")) {
468 REISERFS_SB(s)->s_alloc_options.preallocmin =
469 (value && *value) ? simple_strtoul (value, &value, 0) : 4;
473 if (!strcmp(this_char, "preallocsize")) {
474 REISERFS_SB(s)->s_alloc_options.preallocsize =
475 (value && *value) ? simple_strtoul (value, &value, 0) : PREALLOCATION_SIZE;
479 reiserfs_warning (s, "zam-4001: %s : unknown option - %s",
480 __FUNCTION__ , this_char);
487 static inline void new_hashed_relocation (reiserfs_blocknr_hint_t * hint)
490 if (hint->formatted_node) {
491 hash_in = (char*)&hint->key.k_dir_id;
494 //hint->search_start = hint->beg;
495 hash_in = (char*)&hint->key.k_dir_id;
497 if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
498 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
500 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
503 hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
506 static inline void get_left_neighbor(reiserfs_blocknr_hint_t *hint)
509 struct buffer_head * bh;
510 struct item_head * ih;
514 if (!hint->path) /* reiserfs code can call this function w/o pointer to path
515 * structure supplied; then we rely on supplied search_start */
519 bh = get_last_bh(path);
520 RFALSE( !bh, "green-4002: Illegal path specified to get_left_neighbor");
522 pos_in_item = path->pos_in_item;
523 item = get_item (path);
525 hint->search_start = bh->b_blocknr;
527 if (!hint->formatted_node && is_indirect_le_ih (ih)) {
528 /* for indirect item: go to left and look for the first non-hole entry
529 in the indirect item */
530 if (pos_in_item == I_UNFM_NUM (ih))
532 // pos_in_item = I_UNFM_NUM (ih) - 1;
533 while (pos_in_item >= 0) {
534 int t=get_block_num(item,pos_in_item);
536 hint->search_start = t;
544 /* does result value fit into specified region? */
548 /* should be, if formatted node, then try to put on first part of the device
549 specified as number of percent with mount option device, else try to put
550 on last of device. This is not to say it is good code to do so,
551 but the effect should be measured. */
552 static inline void set_border_in_hint(struct super_block *s, reiserfs_blocknr_hint_t *hint)
554 b_blocknr_t border = SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
556 if (hint->formatted_node)
557 hint->end = border - 1;
562 static inline void displace_large_file(reiserfs_blocknr_hint_t *hint)
564 if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
565 hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), 4) % (hint->end - hint->beg);
567 hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), 4) % (hint->end - hint->beg);
570 static inline void hash_formatted_node(reiserfs_blocknr_hint_t *hint)
575 hash_in = (char*)&hint->key.k_dir_id;
576 else if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
577 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
579 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
581 hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
584 static inline int this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *hint)
586 return hint->block == REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
589 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
590 static inline void displace_new_packing_locality (reiserfs_blocknr_hint_t *hint)
592 struct key * key = &hint->key;
594 hint->th->displace_new_blocks = 0;
595 hint->search_start = hint->beg + keyed_hash((char*)(&key->k_objectid),4) % (hint->end - hint->beg);
599 static inline int old_hashed_relocation (reiserfs_blocknr_hint_t * hint)
604 if (hint->formatted_node || hint->inode == NULL) {
608 hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
609 border = hint->beg + (u32) keyed_hash(((char *) (&hash_in)), 4) % (hint->end - hint->beg - 1);
610 if (border > hint->search_start)
611 hint->search_start = border;
616 static inline int old_way (reiserfs_blocknr_hint_t * hint)
620 if (hint->formatted_node || hint->inode == NULL) {
624 border = hint->beg + le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end - hint->beg);
625 if (border > hint->search_start)
626 hint->search_start = border;
631 static inline void hundredth_slices (reiserfs_blocknr_hint_t * hint)
633 struct key * key = &hint->key;
634 b_blocknr_t slice_start;
636 slice_start = (keyed_hash((char*)(&key->k_dir_id),4) % 100) * (hint->end / 100);
637 if ( slice_start > hint->search_start || slice_start + (hint->end / 100) <= hint->search_start) {
638 hint->search_start = slice_start;
642 static inline void determine_search_start(reiserfs_blocknr_hint_t *hint,
645 struct super_block *s = hint->th->t_super;
647 hint->end = SB_BLOCK_COUNT(s) - 1;
649 /* This is former border algorithm. Now with tunable border offset */
650 if (concentrating_formatted_nodes(s))
651 set_border_in_hint(s, hint);
653 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
654 /* whenever we create a new directory, we displace it. At first we will
655 hash for location, later we might look for a moderately empty place for
657 if (displacing_new_packing_localities(s)
658 && hint->th->displace_new_blocks) {
659 displace_new_packing_locality(hint);
661 /* we do not continue determine_search_start,
662 * if new packing locality is being displaced */
667 /* all persons should feel encouraged to add more special cases here and
670 if (displacing_large_files(s) && !hint->formatted_node
671 && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
672 displace_large_file(hint);
676 /* attempt to copy a feature from old block allocator code */
677 if (TEST_OPTION(old_hashed_relocation, s) && !hint->formatted_node) {
678 old_hashed_relocation(hint);
681 /* if none of our special cases is relevant, use the left neighbor in the
682 tree order of the new node we are allocating for */
683 if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes,s)) {
684 hash_formatted_node(hint);
688 get_left_neighbor(hint);
690 /* Mimic old block allocator behaviour, that is if VFS allowed for preallocation,
691 new blocks are displaced based on directory ID. Also, if suggested search_start
692 is less than last preallocated block, we start searching from it, assuming that
693 HDD dataflow is faster in forward direction */
694 if ( TEST_OPTION(old_way, s)) {
695 if (!hint->formatted_node) {
696 if ( !reiserfs_hashed_relocation(s))
698 else if (!reiserfs_no_unhashed_relocation(s))
699 old_hashed_relocation(hint);
701 if ( hint->inode && hint->search_start < REISERFS_I(hint->inode)->i_prealloc_block)
702 hint->search_start = REISERFS_I(hint->inode)->i_prealloc_block;
707 /* This is an approach proposed by Hans */
708 if ( TEST_OPTION(hundredth_slices, s) && ! (displacing_large_files(s) && !hint->formatted_node)) {
709 hundredth_slices(hint);
713 if (TEST_OPTION(old_hashed_relocation, s))
714 old_hashed_relocation(hint);
715 if (TEST_OPTION(new_hashed_relocation, s))
716 new_hashed_relocation(hint);
720 static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
722 /* make minimum size a mount option and benchmark both ways */
723 /* we preallocate blocks only for regular files, specific size */
724 /* benchmark preallocating always and see what happens */
726 hint->prealloc_size = 0;
728 if (!hint->formatted_node && hint->preallocate) {
729 if (S_ISREG(hint->inode->i_mode)
730 && hint->inode->i_size >= REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocmin * hint->inode->i_sb->s_blocksize)
731 hint->prealloc_size = REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocsize - 1;
736 /* XXX I know it could be merged with upper-level function;
737 but may be result function would be too complex. */
738 static inline int allocate_without_wrapping_disk (reiserfs_blocknr_hint_t * hint,
739 b_blocknr_t * new_blocknrs,
740 b_blocknr_t start, b_blocknr_t finish,
741 int amount_needed, int prealloc_size)
743 int rest = amount_needed;
746 while (rest > 0 && start <= finish) {
747 nr_allocated = scan_bitmap (hint->th, &start, finish, 1,
748 rest + prealloc_size, !hint->formatted_node,
751 if (nr_allocated == 0) /* no new blocks allocated, return */
754 /* fill free_blocknrs array first */
755 while (rest > 0 && nr_allocated > 0) {
756 * new_blocknrs ++ = start ++;
757 rest --; nr_allocated --;
760 /* do we have something to fill prealloc. array also ? */
761 if (nr_allocated > 0) {
762 /* it means prealloc_size was greater that 0 and we do preallocation */
763 list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
764 &SB_JOURNAL(hint->th->t_super)->j_prealloc_list);
765 REISERFS_I(hint->inode)->i_prealloc_block = start;
766 REISERFS_I(hint->inode)->i_prealloc_count = nr_allocated;
771 return (amount_needed - rest);
774 static inline int blocknrs_and_prealloc_arrays_from_search_start
775 (reiserfs_blocknr_hint_t *hint, b_blocknr_t *new_blocknrs, int amount_needed)
777 struct super_block *s = hint->th->t_super;
778 b_blocknr_t start = hint->search_start;
779 b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
781 int nr_allocated = 0;
783 determine_prealloc_size(hint);
784 if (!hint->formatted_node) {
786 #ifdef REISERQUOTA_DEBUG
787 reiserfs_debug (s, "reiserquota: allocating %d blocks id=%u", amount_needed, hint->inode->i_uid);
789 quota_ret = DQUOT_ALLOC_BLOCK_NODIRTY(hint->inode, amount_needed);
790 if (quota_ret) /* Quota exceeded? */
791 return QUOTA_EXCEEDED;
792 if (hint->preallocate && hint->prealloc_size ) {
793 #ifdef REISERQUOTA_DEBUG
794 reiserfs_debug (s, "reiserquota: allocating (prealloc) %d blocks id=%u", hint->prealloc_size, hint->inode->i_uid);
796 quota_ret = DQUOT_PREALLOC_BLOCK_NODIRTY(hint->inode, hint->prealloc_size);
798 hint->preallocate=hint->prealloc_size=0;
803 += allocate_without_wrapping_disk(hint, new_blocknrs + nr_allocated, start, finish,
804 amount_needed - nr_allocated, hint->prealloc_size))
807 /* not all blocks were successfully allocated yet*/
808 if (second_pass) { /* it was a second pass; we must free all blocks */
809 if (!hint->formatted_node) {
810 #ifdef REISERQUOTA_DEBUG
811 reiserfs_debug (s, "reiserquota: freeing (nospace) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated, hint->inode->i_uid);
813 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed + hint->prealloc_size - nr_allocated); /* Free not allocated blocks */
815 while (nr_allocated --)
816 reiserfs_free_block(hint->th, hint->inode, new_blocknrs[nr_allocated], !hint->formatted_node);
818 return NO_DISK_SPACE;
819 } else { /* refine search parameters for next pass */
826 if ( !hint->formatted_node &&
827 amount_needed + hint->prealloc_size >
828 nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
829 /* Some of preallocation blocks were not allocated */
830 #ifdef REISERQUOTA_DEBUG
831 reiserfs_debug (s, "reiserquota: freeing (failed prealloc) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated - INODE_INFO(hint->inode)->i_prealloc_count, hint->inode->i_uid);
833 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed +
834 hint->prealloc_size - nr_allocated -
835 REISERFS_I(hint->inode)->i_prealloc_count);
841 /* grab new blocknrs from preallocated list */
842 /* return amount still needed after using them */
843 static int use_preallocated_list_if_available (reiserfs_blocknr_hint_t *hint,
844 b_blocknr_t *new_blocknrs, int amount_needed)
846 struct inode * inode = hint->inode;
848 if (REISERFS_I(inode)->i_prealloc_count > 0) {
849 while (amount_needed) {
851 *new_blocknrs ++ = REISERFS_I(inode)->i_prealloc_block ++;
852 REISERFS_I(inode)->i_prealloc_count --;
856 if (REISERFS_I(inode)->i_prealloc_count <= 0) {
857 list_del(&REISERFS_I(inode)->i_prealloc_list);
862 /* return amount still needed after using preallocated blocks */
863 return amount_needed;
866 int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
867 b_blocknr_t * new_blocknrs, int amount_needed,
868 int reserved_by_us /* Amount of blocks we have
871 int initial_amount_needed = amount_needed;
874 /* Check if there is enough space, taking into account reserved space */
875 if ( SB_FREE_BLOCKS(hint->th->t_super) - REISERFS_SB(hint->th->t_super)->reserved_blocks <
876 amount_needed - reserved_by_us)
877 return NO_DISK_SPACE;
878 /* should this be if !hint->inode && hint->preallocate? */
879 /* do you mean hint->formatted_node can be removed ? - Zam */
880 /* hint->formatted_node cannot be removed because we try to access
881 inode information here, and there is often no inode assotiated with
882 metadata allocations - green */
884 if (!hint->formatted_node && hint->preallocate) {
885 amount_needed = use_preallocated_list_if_available
886 (hint, new_blocknrs, amount_needed);
887 if (amount_needed == 0) /* all blocknrs we need we got from
890 new_blocknrs += (initial_amount_needed - amount_needed);
893 /* find search start and save it in hint structure */
894 determine_search_start(hint, amount_needed);
896 /* allocation itself; fill new_blocknrs and preallocation arrays */
897 ret = blocknrs_and_prealloc_arrays_from_search_start
898 (hint, new_blocknrs, amount_needed);
900 /* we used prealloc. list to fill (partially) new_blocknrs array. If final allocation fails we
901 * need to return blocks back to prealloc. list or just free them. -- Zam (I chose second
904 if (ret != CARRY_ON) {
905 while (amount_needed ++ < initial_amount_needed) {
906 reiserfs_free_block(hint->th, hint->inode, *(--new_blocknrs), 1);
912 /* These 2 functions are here to provide blocks reservation to the rest of kernel */
913 /* Reserve @blocks amount of blocks in fs pointed by @sb. Caller must make sure
914 there are actually this much blocks on the FS available */
915 void reiserfs_claim_blocks_to_be_allocated(
916 struct super_block *sb, /* super block of
920 int blocks /* How much to reserve */
924 /* Fast case, if reservation is zero - exit immediately. */
928 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
929 REISERFS_SB(sb)->reserved_blocks += blocks;
930 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
933 /* Unreserve @blocks amount of blocks in fs pointed by @sb */
934 void reiserfs_release_claimed_blocks(
935 struct super_block *sb, /* super block of
939 int blocks /* How much to unreserve */
943 /* Fast case, if unreservation is zero - exit immediately. */
947 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
948 REISERFS_SB(sb)->reserved_blocks -= blocks;
949 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
950 RFALSE( REISERFS_SB(sb)->reserved_blocks < 0, "amount of blocks reserved became zero?");
953 /* This function estimates how much pages we will be able to write to FS
954 used for reiserfs_file_write() purposes for now. */
955 int reiserfs_can_fit_pages ( struct super_block *sb /* superblock of filesystem
956 to estimate space */ )
960 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
961 space = (SB_FREE_BLOCKS(sb) - REISERFS_SB(sb)->reserved_blocks) >> ( PAGE_CACHE_SHIFT - sb->s_blocksize_bits);
962 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
964 return space>0?space:0;