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
33 #define _ALLOC_dirid_groups 10
34 #define _ALLOC_oid_groups 11
35 #define _ALLOC_packing_groups 12
37 #define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
38 #define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
39 #define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
41 #define SET_OPTION(optname) \
43 reiserfs_warning(s, "reiserfs: option \"%s\" is set", #optname); \
44 set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
46 #define TEST_OPTION(optname, s) \
47 test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
49 static inline void get_bit_address (struct super_block * s,
50 b_blocknr_t block, int * bmap_nr, int * offset)
52 /* It is in the bitmap block number equal to the block
53 * number divided by the number of bits in a block. */
54 *bmap_nr = block / (s->s_blocksize << 3);
55 /* Within that bitmap block it is located at bit offset *offset. */
56 *offset = block & ((s->s_blocksize << 3) - 1 );
60 #ifdef CONFIG_REISERFS_CHECK
61 int is_reusable (struct super_block * s, b_blocknr_t block, int bit_value)
65 if (block == 0 || block >= SB_BLOCK_COUNT (s)) {
66 reiserfs_warning (s, "vs-4010: is_reusable: block number is out of range %lu (%u)",
67 block, SB_BLOCK_COUNT (s));
71 /* it can't be one of the bitmap blocks */
72 for (i = 0; i < SB_BMAP_NR (s); i ++)
73 if (block == SB_AP_BITMAP (s)[i].bh->b_blocknr) {
74 reiserfs_warning (s, "vs: 4020: is_reusable: "
75 "bitmap block %lu(%u) can't be freed or reused",
76 block, SB_BMAP_NR (s));
80 get_bit_address (s, block, &i, &j);
82 if (i >= SB_BMAP_NR (s)) {
83 reiserfs_warning (s, "vs-4030: is_reusable: there is no so many bitmap blocks: "
84 "block=%lu, bitmap_nr=%d", block, i);
88 if ((bit_value == 0 &&
89 reiserfs_test_le_bit(j, SB_AP_BITMAP(s)[i].bh->b_data)) ||
91 reiserfs_test_le_bit(j, SB_AP_BITMAP (s)[i].bh->b_data) == 0)) {
92 reiserfs_warning (s, "vs-4040: is_reusable: corresponding bit of block %lu does not "
93 "match required value (i==%d, j==%d) test_bit==%d",
94 block, i, j, reiserfs_test_le_bit (j, SB_AP_BITMAP (s)[i].bh->b_data));
99 if (bit_value == 0 && block == SB_ROOT_BLOCK (s)) {
100 reiserfs_warning (s, "vs-4050: is_reusable: this is root block (%u), "
101 "it must be busy", SB_ROOT_BLOCK (s));
107 #endif /* CONFIG_REISERFS_CHECK */
109 /* searches in journal structures for a given block number (bmap, off). If block
110 is found in reiserfs journal it suggests next free block candidate to test. */
111 static inline int is_block_in_journal (struct super_block * s, int bmap, int
116 if (reiserfs_in_journal (s, bmap, off, 1, &tmp)) {
117 if (tmp) { /* hint supplied */
119 PROC_INFO_INC( s, scan_bitmap.in_journal_hint );
121 (*next) = off + 1; /* inc offset to avoid looping. */
122 PROC_INFO_INC( s, scan_bitmap.in_journal_nohint );
124 PROC_INFO_INC( s, scan_bitmap.retry );
130 /* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
132 static int scan_bitmap_block (struct reiserfs_transaction_handle *th,
133 int bmap_n, int *beg, int boundary, int min, int max, int unfm)
135 struct super_block *s = th->t_super;
136 struct reiserfs_bitmap_info *bi=&SB_AP_BITMAP(s)[bmap_n];
140 RFALSE(bmap_n >= SB_BMAP_NR (s), "Bitmap %d is out of range (0..%d)",bmap_n, SB_BMAP_NR (s) - 1);
141 PROC_INFO_INC( s, scan_bitmap.bmap );
142 /* this is unclear and lacks comments, explain how journal bitmaps
143 work here for the reader. Convey a sense of the design here. What
145 /* - I mean `a window of zero bits' as in description of this function - Zam. */
148 reiserfs_warning (s, "NULL bitmap info pointer for bitmap %d", bmap_n);
151 if (buffer_locked (bi->bh)) {
152 PROC_INFO_INC( s, scan_bitmap.wait );
153 __wait_on_buffer (bi->bh);
158 if (bi->free_count < min)
159 return 0; // No free blocks in this bitmap
161 /* search for a first zero bit -- beggining of a window */
162 *beg = reiserfs_find_next_zero_le_bit
163 ((unsigned long*)(bi->bh->b_data), boundary, *beg);
165 if (*beg + min > boundary) { /* search for a zero bit fails or the rest of bitmap block
166 * cannot contain a zero window of minimum size */
170 if (unfm && is_block_in_journal(s,bmap_n, *beg, beg))
172 /* first zero bit found; we check next bits */
173 for (end = *beg + 1;; end ++) {
174 if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit (end, bi->bh->b_data)) {
178 /* finding the other end of zero bit window requires looking into journal structures (in
179 * case of searching for free blocks for unformatted nodes) */
180 if (unfm && is_block_in_journal(s, bmap_n, end, &next))
184 /* now (*beg) points to beginning of zero bits window,
185 * (end) points to one bit after the window end */
186 if (end - *beg >= min) { /* it seems we have found window of proper size */
188 reiserfs_prepare_for_journal (s, bi->bh, 1);
189 /* try to set all blocks used checking are they still free */
190 for (i = *beg; i < end; i++) {
191 /* It seems that we should not check in journal again. */
192 if (reiserfs_test_and_set_le_bit (i, bi->bh->b_data)) {
193 /* bit was set by another process
194 * while we slept in prepare_for_journal() */
195 PROC_INFO_INC( s, scan_bitmap.stolen );
196 if (i >= *beg + min) { /* we can continue with smaller set of allocated blocks,
197 * if length of this set is more or equal to `min' */
201 /* otherwise we clear all bit were set ... */
203 reiserfs_test_and_clear_le_bit (i, bi->bh->b_data);
204 reiserfs_restore_prepared_buffer (s, bi->bh);
206 /* ... and search again in current block from beginning */
210 bi->free_count -= (end - *beg);
211 journal_mark_dirty (th, s, bi->bh);
213 /* free block count calculation */
214 reiserfs_prepare_for_journal (s, SB_BUFFER_WITH_SB(s), 1);
215 PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
216 journal_mark_dirty (th, s, SB_BUFFER_WITH_SB(s));
225 static int bmap_hash_id(struct super_block *s, u32 id) {
226 char * hash_in = NULL;
233 hash_in = (char *)(&id);
234 hash = keyed_hash(hash_in, 4);
235 bm = hash % SB_BMAP_NR(s);
243 * hashes the id and then returns > 0 if the block group for the
244 * corresponding hash is full
246 static inline int block_group_used(struct super_block *s, u32 id) {
248 bm = bmap_hash_id(s, id);
249 if (SB_AP_BITMAP(s)[bm].free_count > ((s->s_blocksize << 3) * 60 / 100) ) {
256 * the packing is returned in disk byte order
258 u32 reiserfs_choose_packing(struct inode *dir) {
260 if (TEST_OPTION(packing_groups, dir->i_sb)) {
261 u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
263 * some versions of reiserfsck expect packing locality 1 to be
266 if (parent_dir == 1 || block_group_used(dir->i_sb,parent_dir))
267 packing = INODE_PKEY(dir)->k_objectid;
269 packing = INODE_PKEY(dir)->k_dir_id;
271 packing = INODE_PKEY(dir)->k_objectid;
275 /* Tries to find contiguous zero bit window (given size) in given region of
276 * bitmap and place new blocks there. Returns number of allocated blocks. */
277 static int scan_bitmap (struct reiserfs_transaction_handle *th,
278 b_blocknr_t *start, b_blocknr_t finish,
279 int min, int max, int unfm, unsigned long file_block)
282 struct super_block * s = th->t_super;
283 /* find every bm and bmap and bmap_nr in this file, and change them all to bitmap_blocknr
284 * - Hans, it is not a block number - Zam. */
288 int off_max = s->s_blocksize << 3;
290 PROC_INFO_INC( s, scan_bitmap.call );
291 if ( SB_FREE_BLOCKS(s) <= 0)
292 return 0; // No point in looking for more free blocks
294 get_bit_address (s, *start, &bm, &off);
295 get_bit_address (s, finish, &end_bm, &end_off);
297 /* When the bitmap is more than 10% free, anyone can allocate.
298 * When it's less than 10% free, only files that already use the
299 * bitmap are allowed. Once we pass 80% full, this restriction
302 * We do this so that files that grow later still have space close to
303 * their original allocation. This improves locality, and presumably
304 * performance as a result.
306 * This is only an allocation policy and does not make up for getting a
307 * bad hint. Decent hinting must be implemented for this to work well.
309 if ( TEST_OPTION(skip_busy, s) && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s)/20 ) {
310 for (;bm < end_bm; bm++, off = 0) {
311 if ( ( off && (!unfm || (file_block != 0))) || SB_AP_BITMAP(s)[bm].free_count > (s->s_blocksize << 3) / 10 )
312 nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
316 get_bit_address (s, *start, &bm, &off);
319 for (;bm < end_bm; bm++, off = 0) {
320 nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
325 nr_allocated = scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
328 *start = bm * off_max + off;
333 static void _reiserfs_free_block (struct reiserfs_transaction_handle *th,
334 struct inode *inode, b_blocknr_t block,
337 struct super_block * s = th->t_super;
338 struct reiserfs_super_block * rs;
339 struct buffer_head * sbh;
340 struct reiserfs_bitmap_info *apbi;
343 PROC_INFO_INC( s, free_block );
345 rs = SB_DISK_SUPER_BLOCK (s);
346 sbh = SB_BUFFER_WITH_SB (s);
347 apbi = SB_AP_BITMAP(s);
349 get_bit_address (s, block, &nr, &offset);
351 if (nr >= sb_bmap_nr (rs)) {
352 reiserfs_warning (s, "vs-4075: reiserfs_free_block: "
353 "block %lu is out of range on %s",
354 block, reiserfs_bdevname (s));
358 reiserfs_prepare_for_journal(s, apbi[nr].bh, 1 ) ;
360 /* clear bit for the given block in bit map */
361 if (!reiserfs_test_and_clear_le_bit (offset, apbi[nr].bh->b_data)) {
362 reiserfs_warning (s, "vs-4080: reiserfs_free_block: "
363 "free_block (%s:%lu)[dev:blocknr]: bit already cleared",
364 reiserfs_bdevname (s), block);
366 apbi[nr].free_count ++;
367 journal_mark_dirty (th, s, apbi[nr].bh);
369 reiserfs_prepare_for_journal(s, sbh, 1) ;
370 /* update super block */
371 set_sb_free_blocks( rs, sb_free_blocks(rs) + 1 );
373 journal_mark_dirty (th, s, sbh);
375 DQUOT_FREE_BLOCK_NODIRTY(inode, 1);
378 void reiserfs_free_block (struct reiserfs_transaction_handle *th,
379 struct inode *inode, b_blocknr_t block,
382 struct super_block * s = th->t_super;
384 RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
385 RFALSE(is_reusable (s, block, 1) == 0, "vs-4071: can not free such block");
386 /* mark it before we clear it, just in case */
387 journal_mark_freed(th, s, block) ;
388 _reiserfs_free_block(th, inode, block, for_unformatted) ;
391 /* preallocated blocks don't need to be run through journal_mark_freed */
392 void reiserfs_free_prealloc_block (struct reiserfs_transaction_handle *th,
393 struct inode *inode, b_blocknr_t block) {
394 RFALSE(!th->t_super, "vs-4060: trying to free block on nonexistent device");
395 RFALSE(is_reusable (th->t_super, block, 1) == 0, "vs-4070: can not free such block");
396 _reiserfs_free_block(th, inode, block, 1) ;
399 static void __discard_prealloc (struct reiserfs_transaction_handle * th,
400 struct reiserfs_inode_info *ei)
402 unsigned long save = ei->i_prealloc_block ;
404 struct inode *inode = &ei->vfs_inode;
405 #ifdef CONFIG_REISERFS_CHECK
406 if (ei->i_prealloc_count < 0)
407 reiserfs_warning (th->t_super, "zam-4001:%s: inode has negative prealloc blocks count.", __FUNCTION__ );
409 while (ei->i_prealloc_count > 0) {
410 reiserfs_free_prealloc_block(th, inode, ei->i_prealloc_block);
411 ei->i_prealloc_block++;
412 ei->i_prealloc_count --;
416 reiserfs_update_sd(th, inode);
417 ei->i_prealloc_block = save;
418 list_del_init(&(ei->i_prealloc_list));
421 /* FIXME: It should be inline function */
422 void reiserfs_discard_prealloc (struct reiserfs_transaction_handle *th,
425 struct reiserfs_inode_info *ei = REISERFS_I(inode);
426 if (ei->i_prealloc_count)
427 __discard_prealloc(th, ei);
430 void reiserfs_discard_all_prealloc (struct reiserfs_transaction_handle *th)
432 struct list_head * plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
434 while (!list_empty(plist)) {
435 struct reiserfs_inode_info *ei;
436 ei = list_entry(plist->next, struct reiserfs_inode_info, i_prealloc_list);
437 #ifdef CONFIG_REISERFS_CHECK
438 if (!ei->i_prealloc_count) {
439 reiserfs_warning (th->t_super, "zam-4001:%s: inode is in prealloc list but has no preallocated blocks.", __FUNCTION__);
442 __discard_prealloc(th, ei);
446 void reiserfs_init_alloc_options (struct super_block *s)
448 set_bit (_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
449 set_bit (_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
450 set_bit (_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
453 /* block allocator related options are parsed here */
454 int reiserfs_parse_alloc_options(struct super_block * s, char * options)
456 char * this_char, * value;
458 REISERFS_SB(s)->s_alloc_options.bits = 0; /* clear default settings */
460 while ( (this_char = strsep (&options, ":")) != NULL ) {
461 if ((value = strchr (this_char, '=')) != NULL)
464 if (!strcmp(this_char, "concentrating_formatted_nodes")) {
466 SET_OPTION(concentrating_formatted_nodes);
467 temp = (value && *value) ? simple_strtoul (value, &value, 0) : 10;
468 if (temp <= 0 || temp > 100) {
469 REISERFS_SB(s)->s_alloc_options.border = 10;
471 REISERFS_SB(s)->s_alloc_options.border = 100 / temp;
475 if (!strcmp(this_char, "displacing_large_files")) {
476 SET_OPTION(displacing_large_files);
477 REISERFS_SB(s)->s_alloc_options.large_file_size =
478 (value && *value) ? simple_strtoul (value, &value, 0) : 16;
481 if (!strcmp(this_char, "displacing_new_packing_localities")) {
482 SET_OPTION(displacing_new_packing_localities);
486 if (!strcmp(this_char, "old_hashed_relocation")) {
487 SET_OPTION(old_hashed_relocation);
491 if (!strcmp(this_char, "new_hashed_relocation")) {
492 SET_OPTION(new_hashed_relocation);
496 if (!strcmp(this_char, "dirid_groups")) {
497 SET_OPTION(dirid_groups);
500 if (!strcmp(this_char, "oid_groups")) {
501 SET_OPTION(oid_groups);
504 if (!strcmp(this_char, "packing_groups")) {
505 SET_OPTION(packing_groups);
508 if (!strcmp(this_char, "hashed_formatted_nodes")) {
509 SET_OPTION(hashed_formatted_nodes);
513 if (!strcmp(this_char, "skip_busy")) {
514 SET_OPTION(skip_busy);
518 if (!strcmp(this_char, "hundredth_slices")) {
519 SET_OPTION(hundredth_slices);
523 if (!strcmp(this_char, "old_way")) {
528 if (!strcmp(this_char, "displace_based_on_dirid")) {
529 SET_OPTION(displace_based_on_dirid);
533 if (!strcmp(this_char, "preallocmin")) {
534 REISERFS_SB(s)->s_alloc_options.preallocmin =
535 (value && *value) ? simple_strtoul (value, &value, 0) : 4;
539 if (!strcmp(this_char, "preallocsize")) {
540 REISERFS_SB(s)->s_alloc_options.preallocsize =
541 (value && *value) ? simple_strtoul (value, &value, 0) : PREALLOCATION_SIZE;
545 reiserfs_warning (s, "zam-4001: %s : unknown option - %s",
546 __FUNCTION__ , this_char);
550 reiserfs_warning (s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
554 static inline void new_hashed_relocation (reiserfs_blocknr_hint_t * hint)
557 if (hint->formatted_node) {
558 hash_in = (char*)&hint->key.k_dir_id;
561 //hint->search_start = hint->beg;
562 hash_in = (char*)&hint->key.k_dir_id;
564 if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
565 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
567 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
570 hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
574 * Relocation based on dirid, hashing them into a given bitmap block
575 * files. Formatted nodes are unaffected, a seperate policy covers them
578 dirid_groups (reiserfs_blocknr_hint_t *hint)
583 struct super_block *sb = hint->th->t_super;
585 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
586 else if (hint->formatted_node)
587 dirid = hint->key.k_dir_id;
590 bm = bmap_hash_id(sb, dirid);
591 hash = bm * (sb->s_blocksize << 3);
592 /* give a portion of the block group to metadata */
594 hash += sb->s_blocksize/2;
595 hint->search_start = hash;
600 * Relocation based on oid, hashing them into a given bitmap block
601 * files. Formatted nodes are unaffected, a seperate policy covers them
604 oid_groups (reiserfs_blocknr_hint_t *hint)
612 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
614 /* keep the root dir and it's first set of subdirs close to
615 * the start of the disk
618 hash = (hint->inode->i_sb->s_blocksize << 3);
620 oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
621 bm = bmap_hash_id(hint->inode->i_sb, oid);
622 hash = bm * (hint->inode->i_sb->s_blocksize << 3);
624 hint->search_start = hash;
628 /* returns 1 if it finds an indirect item and gets valid hint info
629 * from it, otherwise 0
631 static int get_left_neighbor(reiserfs_blocknr_hint_t *hint)
634 struct buffer_head * bh;
635 struct item_head * ih;
640 if (!hint->path) /* reiserfs code can call this function w/o pointer to path
641 * structure supplied; then we rely on supplied search_start */
645 bh = get_last_bh(path);
646 RFALSE( !bh, "green-4002: Illegal path specified to get_left_neighbor");
648 pos_in_item = path->pos_in_item;
649 item = get_item (path);
651 hint->search_start = bh->b_blocknr;
653 if (!hint->formatted_node && is_indirect_le_ih (ih)) {
654 /* for indirect item: go to left and look for the first non-hole entry
655 in the indirect item */
656 if (pos_in_item == I_UNFM_NUM (ih))
658 // pos_in_item = I_UNFM_NUM (ih) - 1;
659 while (pos_in_item >= 0) {
660 int t=get_block_num(item,pos_in_item);
662 hint->search_start = t;
670 /* does result value fit into specified region? */
674 /* should be, if formatted node, then try to put on first part of the device
675 specified as number of percent with mount option device, else try to put
676 on last of device. This is not to say it is good code to do so,
677 but the effect should be measured. */
678 static inline void set_border_in_hint(struct super_block *s, reiserfs_blocknr_hint_t *hint)
680 b_blocknr_t border = SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
682 if (hint->formatted_node)
683 hint->end = border - 1;
688 static inline void displace_large_file(reiserfs_blocknr_hint_t *hint)
690 if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
691 hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), 4) % (hint->end - hint->beg);
693 hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), 4) % (hint->end - hint->beg);
696 static inline void hash_formatted_node(reiserfs_blocknr_hint_t *hint)
701 hash_in = (char*)&hint->key.k_dir_id;
702 else if ( TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
703 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
705 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
707 hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
710 static inline int this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *hint)
712 return hint->block == REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
715 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
716 static inline void displace_new_packing_locality (reiserfs_blocknr_hint_t *hint)
718 struct key * key = &hint->key;
720 hint->th->displace_new_blocks = 0;
721 hint->search_start = hint->beg + keyed_hash((char*)(&key->k_objectid),4) % (hint->end - hint->beg);
725 static inline int old_hashed_relocation (reiserfs_blocknr_hint_t * hint)
730 if (hint->formatted_node || hint->inode == NULL) {
734 hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
735 border = hint->beg + (u32) keyed_hash(((char *) (&hash_in)), 4) % (hint->end - hint->beg - 1);
736 if (border > hint->search_start)
737 hint->search_start = border;
742 static inline int old_way (reiserfs_blocknr_hint_t * hint)
746 if (hint->formatted_node || hint->inode == NULL) {
750 border = hint->beg + le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end - hint->beg);
751 if (border > hint->search_start)
752 hint->search_start = border;
757 static inline void hundredth_slices (reiserfs_blocknr_hint_t * hint)
759 struct key * key = &hint->key;
760 b_blocknr_t slice_start;
762 slice_start = (keyed_hash((char*)(&key->k_dir_id),4) % 100) * (hint->end / 100);
763 if ( slice_start > hint->search_start || slice_start + (hint->end / 100) <= hint->search_start) {
764 hint->search_start = slice_start;
768 static void determine_search_start(reiserfs_blocknr_hint_t *hint,
771 struct super_block *s = hint->th->t_super;
775 hint->end = SB_BLOCK_COUNT(s) - 1;
777 /* This is former border algorithm. Now with tunable border offset */
778 if (concentrating_formatted_nodes(s))
779 set_border_in_hint(s, hint);
781 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
782 /* whenever we create a new directory, we displace it. At first we will
783 hash for location, later we might look for a moderately empty place for
785 if (displacing_new_packing_localities(s)
786 && hint->th->displace_new_blocks) {
787 displace_new_packing_locality(hint);
789 /* we do not continue determine_search_start,
790 * if new packing locality is being displaced */
795 /* all persons should feel encouraged to add more special cases here and
798 if (displacing_large_files(s) && !hint->formatted_node
799 && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
800 displace_large_file(hint);
804 /* if none of our special cases is relevant, use the left neighbor in the
805 tree order of the new node we are allocating for */
806 if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes,s)) {
807 hash_formatted_node(hint);
811 unfm_hint = get_left_neighbor(hint);
813 /* Mimic old block allocator behaviour, that is if VFS allowed for preallocation,
814 new blocks are displaced based on directory ID. Also, if suggested search_start
815 is less than last preallocated block, we start searching from it, assuming that
816 HDD dataflow is faster in forward direction */
817 if ( TEST_OPTION(old_way, s)) {
818 if (!hint->formatted_node) {
819 if ( !reiserfs_hashed_relocation(s))
821 else if (!reiserfs_no_unhashed_relocation(s))
822 old_hashed_relocation(hint);
824 if ( hint->inode && hint->search_start < REISERFS_I(hint->inode)->i_prealloc_block)
825 hint->search_start = REISERFS_I(hint->inode)->i_prealloc_block;
830 /* This is an approach proposed by Hans */
831 if ( TEST_OPTION(hundredth_slices, s) && ! (displacing_large_files(s) && !hint->formatted_node)) {
832 hundredth_slices(hint);
836 /* old_hashed_relocation only works on unformatted */
837 if (!unfm_hint && !hint->formatted_node &&
838 TEST_OPTION(old_hashed_relocation, s))
840 old_hashed_relocation(hint);
842 /* new_hashed_relocation works with both formatted/unformatted nodes */
843 if ((!unfm_hint || hint->formatted_node) &&
844 TEST_OPTION(new_hashed_relocation, s))
846 new_hashed_relocation(hint);
848 /* dirid grouping works only on unformatted nodes */
849 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups,s))
854 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
855 if (hint->formatted_node && TEST_OPTION(dirid_groups,s))
861 /* oid grouping works only on unformatted nodes */
862 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups,s))
869 static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
871 /* make minimum size a mount option and benchmark both ways */
872 /* we preallocate blocks only for regular files, specific size */
873 /* benchmark preallocating always and see what happens */
875 hint->prealloc_size = 0;
877 if (!hint->formatted_node && hint->preallocate) {
878 if (S_ISREG(hint->inode->i_mode)
879 && hint->inode->i_size >= REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocmin * hint->inode->i_sb->s_blocksize)
880 hint->prealloc_size = REISERFS_SB(hint->th->t_super)->s_alloc_options.preallocsize - 1;
885 /* XXX I know it could be merged with upper-level function;
886 but may be result function would be too complex. */
887 static inline int allocate_without_wrapping_disk (reiserfs_blocknr_hint_t * hint,
888 b_blocknr_t * new_blocknrs,
889 b_blocknr_t start, b_blocknr_t finish,
891 int amount_needed, int prealloc_size)
893 int rest = amount_needed;
896 while (rest > 0 && start <= finish) {
897 nr_allocated = scan_bitmap (hint->th, &start, finish, min,
898 rest + prealloc_size, !hint->formatted_node,
901 if (nr_allocated == 0) /* no new blocks allocated, return */
904 /* fill free_blocknrs array first */
905 while (rest > 0 && nr_allocated > 0) {
906 * new_blocknrs ++ = start ++;
907 rest --; nr_allocated --;
910 /* do we have something to fill prealloc. array also ? */
911 if (nr_allocated > 0) {
912 /* it means prealloc_size was greater that 0 and we do preallocation */
913 list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
914 &SB_JOURNAL(hint->th->t_super)->j_prealloc_list);
915 REISERFS_I(hint->inode)->i_prealloc_block = start;
916 REISERFS_I(hint->inode)->i_prealloc_count = nr_allocated;
921 return (amount_needed - rest);
924 static inline int blocknrs_and_prealloc_arrays_from_search_start
925 (reiserfs_blocknr_hint_t *hint, b_blocknr_t *new_blocknrs, int amount_needed)
927 struct super_block *s = hint->th->t_super;
928 b_blocknr_t start = hint->search_start;
929 b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
931 int nr_allocated = 0;
934 determine_prealloc_size(hint);
935 if (!hint->formatted_node) {
937 #ifdef REISERQUOTA_DEBUG
938 reiserfs_debug (s, "reiserquota: allocating %d blocks id=%u", amount_needed, hint->inode->i_uid);
940 quota_ret = DQUOT_ALLOC_BLOCK_NODIRTY(hint->inode, amount_needed);
941 if (quota_ret) /* Quota exceeded? */
942 return QUOTA_EXCEEDED;
943 if (hint->preallocate && hint->prealloc_size ) {
944 #ifdef REISERQUOTA_DEBUG
945 reiserfs_debug (s, "reiserquota: allocating (prealloc) %d blocks id=%u", hint->prealloc_size, hint->inode->i_uid);
947 quota_ret = DQUOT_PREALLOC_BLOCK_NODIRTY(hint->inode, hint->prealloc_size);
949 hint->preallocate=hint->prealloc_size=0;
951 /* for unformatted nodes, force large allocations */
952 bigalloc = amount_needed;
956 /* in bigalloc mode, nr_allocated should stay zero until
957 * the entire allocation is filled
959 if (unlikely(bigalloc && nr_allocated)) {
960 reiserfs_warning(s, "bigalloc is %d, nr_allocated %d\n",
961 bigalloc, nr_allocated);
962 /* reset things to a sane value */
963 bigalloc = amount_needed - nr_allocated;
966 * try pass 0 and pass 1 looking for a nice big
967 * contiguous allocation. Then reset and look
968 * for anything you can find.
970 if (passno == 2 && bigalloc) {
975 case 0: /* Search from hint->search_start to end of disk */
976 start = hint->search_start;
977 finish = SB_BLOCK_COUNT(s) - 1;
979 case 1: /* Search from hint->beg to hint->search_start */
981 finish = hint->search_start;
983 case 2: /* Last chance: Search from 0 to hint->beg */
987 default: /* We've tried searching everywhere, not enough space */
988 /* Free the blocks */
989 if (!hint->formatted_node) {
990 #ifdef REISERQUOTA_DEBUG
991 reiserfs_debug (s, "reiserquota: freeing (nospace) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated, hint->inode->i_uid);
993 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed + hint->prealloc_size - nr_allocated); /* Free not allocated blocks */
995 while (nr_allocated --)
996 reiserfs_free_block(hint->th, hint->inode, new_blocknrs[nr_allocated], !hint->formatted_node);
998 return NO_DISK_SPACE;
1000 } while ((nr_allocated += allocate_without_wrapping_disk (hint,
1001 new_blocknrs + nr_allocated, start, finish,
1002 bigalloc ? bigalloc : 1,
1003 amount_needed - nr_allocated,
1004 hint->prealloc_size))
1006 if ( !hint->formatted_node &&
1007 amount_needed + hint->prealloc_size >
1008 nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
1009 /* Some of preallocation blocks were not allocated */
1010 #ifdef REISERQUOTA_DEBUG
1011 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);
1013 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed +
1014 hint->prealloc_size - nr_allocated -
1015 REISERFS_I(hint->inode)->i_prealloc_count);
1021 /* grab new blocknrs from preallocated list */
1022 /* return amount still needed after using them */
1023 static int use_preallocated_list_if_available (reiserfs_blocknr_hint_t *hint,
1024 b_blocknr_t *new_blocknrs, int amount_needed)
1026 struct inode * inode = hint->inode;
1028 if (REISERFS_I(inode)->i_prealloc_count > 0) {
1029 while (amount_needed) {
1031 *new_blocknrs ++ = REISERFS_I(inode)->i_prealloc_block ++;
1032 REISERFS_I(inode)->i_prealloc_count --;
1036 if (REISERFS_I(inode)->i_prealloc_count <= 0) {
1037 list_del(&REISERFS_I(inode)->i_prealloc_list);
1042 /* return amount still needed after using preallocated blocks */
1043 return amount_needed;
1046 int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
1047 b_blocknr_t * new_blocknrs, int amount_needed,
1048 int reserved_by_us /* Amount of blocks we have
1049 already reserved */)
1051 int initial_amount_needed = amount_needed;
1054 /* Check if there is enough space, taking into account reserved space */
1055 if ( SB_FREE_BLOCKS(hint->th->t_super) - REISERFS_SB(hint->th->t_super)->reserved_blocks <
1056 amount_needed - reserved_by_us)
1057 return NO_DISK_SPACE;
1058 /* should this be if !hint->inode && hint->preallocate? */
1059 /* do you mean hint->formatted_node can be removed ? - Zam */
1060 /* hint->formatted_node cannot be removed because we try to access
1061 inode information here, and there is often no inode assotiated with
1062 metadata allocations - green */
1064 if (!hint->formatted_node && hint->preallocate) {
1065 amount_needed = use_preallocated_list_if_available
1066 (hint, new_blocknrs, amount_needed);
1067 if (amount_needed == 0) /* all blocknrs we need we got from
1070 new_blocknrs += (initial_amount_needed - amount_needed);
1073 /* find search start and save it in hint structure */
1074 determine_search_start(hint, amount_needed);
1076 /* allocation itself; fill new_blocknrs and preallocation arrays */
1077 ret = blocknrs_and_prealloc_arrays_from_search_start
1078 (hint, new_blocknrs, amount_needed);
1080 /* we used prealloc. list to fill (partially) new_blocknrs array. If final allocation fails we
1081 * need to return blocks back to prealloc. list or just free them. -- Zam (I chose second
1084 if (ret != CARRY_ON) {
1085 while (amount_needed ++ < initial_amount_needed) {
1086 reiserfs_free_block(hint->th, hint->inode, *(--new_blocknrs), 1);
1092 /* These 2 functions are here to provide blocks reservation to the rest of kernel */
1093 /* Reserve @blocks amount of blocks in fs pointed by @sb. Caller must make sure
1094 there are actually this much blocks on the FS available */
1095 void reiserfs_claim_blocks_to_be_allocated(
1096 struct super_block *sb, /* super block of
1100 int blocks /* How much to reserve */
1104 /* Fast case, if reservation is zero - exit immediately. */
1108 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
1109 REISERFS_SB(sb)->reserved_blocks += blocks;
1110 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
1113 /* Unreserve @blocks amount of blocks in fs pointed by @sb */
1114 void reiserfs_release_claimed_blocks(
1115 struct super_block *sb, /* super block of
1119 int blocks /* How much to unreserve */
1123 /* Fast case, if unreservation is zero - exit immediately. */
1127 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
1128 REISERFS_SB(sb)->reserved_blocks -= blocks;
1129 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
1130 RFALSE( REISERFS_SB(sb)->reserved_blocks < 0, "amount of blocks reserved became zero?");
1133 /* This function estimates how much pages we will be able to write to FS
1134 used for reiserfs_file_write() purposes for now. */
1135 int reiserfs_can_fit_pages ( struct super_block *sb /* superblock of filesystem
1136 to estimate space */ )
1140 spin_lock(&REISERFS_SB(sb)->bitmap_lock);
1141 space = (SB_FREE_BLOCKS(sb) - REISERFS_SB(sb)->reserved_blocks) >> ( PAGE_CACHE_SHIFT - sb->s_blocksize_bits);
1142 spin_unlock(&REISERFS_SB(sb)->bitmap_lock);
1144 return space>0?space:0;