| Author | Tokens | Token Proportion | Commits | Commit Proportion |
|---|---|---|---|---|
| Oleg Drokin | 2784 | 42.46% | 4 | 5.13% |
| Linus Torvalds | 1043 | 15.91% | 10 | 12.82% |
| Jeff Mahoney | 837 | 12.77% | 18 | 23.08% |
| Chris Mason | 799 | 12.19% | 3 | 3.85% |
| Jan Kara | 572 | 8.72% | 3 | 3.85% |
| Andrew Morton | 347 | 5.29% | 5 | 6.41% |
| Linus Torvalds (pre-git) | 111 | 1.69% | 16 | 20.51% |
| Dave Jones | 18 | 0.27% | 3 | 3.85% |
| Frédéric Weisbecker | 12 | 0.18% | 2 | 2.56% |
| Akinobu Mita | 7 | 0.11% | 2 | 2.56% |
| Christoph Hellwig | 7 | 0.11% | 2 | 2.56% |
| Al Viro | 6 | 0.09% | 3 | 3.85% |
| Kees Cook | 5 | 0.08% | 1 | 1.28% |
| Joe Perches | 2 | 0.03% | 1 | 1.28% |
| Eric Sesterhenn / Snakebyte | 2 | 0.03% | 1 | 1.28% |
| Harvey Harrison | 1 | 0.02% | 1 | 1.28% |
| Josef 'Jeff' Sipek | 1 | 0.02% | 1 | 1.28% |
| Daniel Mack | 1 | 0.02% | 1 | 1.28% |
| Adrian Bunk | 1 | 0.02% | 1 | 1.28% |
| Total | 6556 | 78 |
/* * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README */ /* Reiserfs block (de)allocator, bitmap-based. */ #include <linux/time.h> #include "reiserfs.h" #include <linux/errno.h> #include <linux/buffer_head.h> #include <linux/kernel.h> #include <linux/pagemap.h> #include <linux/vmalloc.h> #include <linux/quotaops.h> #include <linux/seq_file.h> #define PREALLOCATION_SIZE 9 /* different reiserfs block allocator options */ #define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits) #define _ALLOC_concentrating_formatted_nodes 0 #define _ALLOC_displacing_large_files 1 #define _ALLOC_displacing_new_packing_localities 2 #define _ALLOC_old_hashed_relocation 3 #define _ALLOC_new_hashed_relocation 4 #define _ALLOC_skip_busy 5 #define _ALLOC_displace_based_on_dirid 6 #define _ALLOC_hashed_formatted_nodes 7 #define _ALLOC_old_way 8 #define _ALLOC_hundredth_slices 9 #define _ALLOC_dirid_groups 10 #define _ALLOC_oid_groups 11 #define _ALLOC_packing_groups 12 #define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s)) #define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s)) #define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s)) #define SET_OPTION(optname) \ do { \ reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \ set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \ } while(0) #define TEST_OPTION(optname, s) \ test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)) static inline void get_bit_address(struct super_block *s, b_blocknr_t block, unsigned int *bmap_nr, unsigned int *offset) { /* * It is in the bitmap block number equal to the block * number divided by the number of bits in a block. */ *bmap_nr = block >> (s->s_blocksize_bits + 3); /* Within that bitmap block it is located at bit offset *offset. */ *offset = block & ((s->s_blocksize << 3) - 1); } int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value) { unsigned int bmap, offset; unsigned int bmap_count = reiserfs_bmap_count(s); if (block == 0 || block >= SB_BLOCK_COUNT(s)) { reiserfs_error(s, "vs-4010", "block number is out of range %lu (%u)", block, SB_BLOCK_COUNT(s)); return 0; } get_bit_address(s, block, &bmap, &offset); /* * Old format filesystem? Unlikely, but the bitmaps are all * up front so we need to account for it. */ if (unlikely(test_bit(REISERFS_OLD_FORMAT, &REISERFS_SB(s)->s_properties))) { b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1; if (block >= bmap1 && block <= bmap1 + bmap_count) { reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) " "can't be freed or reused", block, bmap_count); return 0; } } else { if (offset == 0) { reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) " "can't be freed or reused", block, bmap_count); return 0; } } if (bmap >= bmap_count) { reiserfs_error(s, "vs-4030", "bitmap for requested block " "is out of range: block=%lu, bitmap_nr=%u", block, bmap); return 0; } if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) { reiserfs_error(s, "vs-4050", "this is root block (%u), " "it must be busy", SB_ROOT_BLOCK(s)); return 0; } return 1; } /* * Searches in journal structures for a given block number (bmap, off). * If block is found in reiserfs journal it suggests next free block * candidate to test. */ static inline int is_block_in_journal(struct super_block *s, unsigned int bmap, int off, int *next) { b_blocknr_t tmp; if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) { if (tmp) { /* hint supplied */ *next = tmp; PROC_INFO_INC(s, scan_bitmap.in_journal_hint); } else { (*next) = off + 1; /* inc offset to avoid looping. */ PROC_INFO_INC(s, scan_bitmap.in_journal_nohint); } PROC_INFO_INC(s, scan_bitmap.retry); return 1; } return 0; } /* * Searches for a window of zero bits with given minimum and maximum * lengths in one bitmap block */ static int scan_bitmap_block(struct reiserfs_transaction_handle *th, unsigned int bmap_n, int *beg, int boundary, int min, int max, int unfm) { struct super_block *s = th->t_super; struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n]; struct buffer_head *bh; int end, next; int org = *beg; BUG_ON(!th->t_trans_id); RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of " "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1); PROC_INFO_INC(s, scan_bitmap.bmap); if (!bi) { reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer " "for bitmap %d", bmap_n); return 0; } bh = reiserfs_read_bitmap_block(s, bmap_n); if (bh == NULL) return 0; while (1) { cont: if (bi->free_count < min) { brelse(bh); return 0; /* No free blocks in this bitmap */ } /* search for a first zero bit -- beginning of a window */ *beg = reiserfs_find_next_zero_le_bit ((unsigned long *)(bh->b_data), boundary, *beg); /* * search for a zero bit fails or the rest of bitmap block * cannot contain a zero window of minimum size */ if (*beg + min > boundary) { brelse(bh); return 0; } if (unfm && is_block_in_journal(s, bmap_n, *beg, beg)) continue; /* first zero bit found; we check next bits */ for (end = *beg + 1;; end++) { if (end >= *beg + max || end >= boundary || reiserfs_test_le_bit(end, bh->b_data)) { next = end; break; } /* * finding the other end of zero bit window requires * looking into journal structures (in case of * searching for free blocks for unformatted nodes) */ if (unfm && is_block_in_journal(s, bmap_n, end, &next)) break; } /* * now (*beg) points to beginning of zero bits window, * (end) points to one bit after the window end */ /* found window of proper size */ if (end - *beg >= min) { int i; reiserfs_prepare_for_journal(s, bh, 1); /* * try to set all blocks used checking are * they still free */ for (i = *beg; i < end; i++) { /* Don't check in journal again. */ if (reiserfs_test_and_set_le_bit (i, bh->b_data)) { /* * bit was set by another process while * we slept in prepare_for_journal() */ PROC_INFO_INC(s, scan_bitmap.stolen); /* * we can continue with smaller set * of allocated blocks, if length of * this set is more or equal to `min' */ if (i >= *beg + min) { end = i; break; } /* * otherwise we clear all bit * were set ... */ while (--i >= *beg) reiserfs_clear_le_bit (i, bh->b_data); reiserfs_restore_prepared_buffer(s, bh); *beg = org; /* * Search again in current block * from beginning */ goto cont; } } bi->free_count -= (end - *beg); journal_mark_dirty(th, bh); brelse(bh); /* free block count calculation */ reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1); PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg)); journal_mark_dirty(th, SB_BUFFER_WITH_SB(s)); return end - (*beg); } else { *beg = next; } } } static int bmap_hash_id(struct super_block *s, u32 id) { char *hash_in = NULL; unsigned long hash; unsigned bm; if (id <= 2) { bm = 1; } else { hash_in = (char *)(&id); hash = keyed_hash(hash_in, 4); bm = hash % reiserfs_bmap_count(s); if (!bm) bm = 1; } /* this can only be true when SB_BMAP_NR = 1 */ if (bm >= reiserfs_bmap_count(s)) bm = 0; return bm; } /* * hashes the id and then returns > 0 if the block group for the * corresponding hash is full */ static inline int block_group_used(struct super_block *s, u32 id) { int bm = bmap_hash_id(s, id); struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm]; /* * If we don't have cached information on this bitmap block, we're * going to have to load it later anyway. Loading it here allows us * to make a better decision. This favors long-term performance gain * with a better on-disk layout vs. a short term gain of skipping the * read and potentially having a bad placement. */ if (info->free_count == UINT_MAX) { struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm); brelse(bh); } if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) { return 0; } return 1; } /* * the packing is returned in disk byte order */ __le32 reiserfs_choose_packing(struct inode * dir) { __le32 packing; if (TEST_OPTION(packing_groups, dir->i_sb)) { u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id); /* * some versions of reiserfsck expect packing locality 1 to be * special */ if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir)) packing = INODE_PKEY(dir)->k_objectid; else packing = INODE_PKEY(dir)->k_dir_id; } else packing = INODE_PKEY(dir)->k_objectid; return packing; } /* * Tries to find contiguous zero bit window (given size) in given region of * bitmap and place new blocks there. Returns number of allocated blocks. */ static int scan_bitmap(struct reiserfs_transaction_handle *th, b_blocknr_t * start, b_blocknr_t finish, int min, int max, int unfm, sector_t file_block) { int nr_allocated = 0; struct super_block *s = th->t_super; unsigned int bm, off; unsigned int end_bm, end_off; unsigned int off_max = s->s_blocksize << 3; BUG_ON(!th->t_trans_id); PROC_INFO_INC(s, scan_bitmap.call); /* No point in looking for more free blocks */ if (SB_FREE_BLOCKS(s) <= 0) return 0; get_bit_address(s, *start, &bm, &off); get_bit_address(s, finish, &end_bm, &end_off); if (bm > reiserfs_bmap_count(s)) return 0; if (end_bm > reiserfs_bmap_count(s)) end_bm = reiserfs_bmap_count(s); /* * When the bitmap is more than 10% free, anyone can allocate. * When it's less than 10% free, only files that already use the * bitmap are allowed. Once we pass 80% full, this restriction * is lifted. * * We do this so that files that grow later still have space close to * their original allocation. This improves locality, and presumably * performance as a result. * * This is only an allocation policy and does not make up for getting a * bad hint. Decent hinting must be implemented for this to work well. */ if (TEST_OPTION(skip_busy, s) && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) { for (; bm < end_bm; bm++, off = 0) { if ((off && (!unfm || (file_block != 0))) || SB_AP_BITMAP(s)[bm].free_count > (s->s_blocksize << 3) / 10) nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm); if (nr_allocated) goto ret; } /* we know from above that start is a reasonable number */ get_bit_address(s, *start, &bm, &off); } for (; bm < end_bm; bm++, off = 0) { nr_allocated = scan_bitmap_block(th, bm, &off, off_max, min, max, unfm); if (nr_allocated) goto ret; } nr_allocated = scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm); ret: *start = bm * off_max + off; return nr_allocated; } static void _reiserfs_free_block(struct reiserfs_transaction_handle *th, struct inode *inode, b_blocknr_t block, int for_unformatted) { struct super_block *s = th->t_super; struct reiserfs_super_block *rs; struct buffer_head *sbh, *bmbh; struct reiserfs_bitmap_info *apbi; unsigned int nr, offset; BUG_ON(!th->t_trans_id); PROC_INFO_INC(s, free_block); rs = SB_DISK_SUPER_BLOCK(s); sbh = SB_BUFFER_WITH_SB(s); apbi = SB_AP_BITMAP(s); get_bit_address(s, block, &nr, &offset); if (nr >= reiserfs_bmap_count(s)) { reiserfs_error(s, "vs-4075", "block %lu is out of range", block); return; } bmbh = reiserfs_read_bitmap_block(s, nr); if (!bmbh) return; reiserfs_prepare_for_journal(s, bmbh, 1); /* clear bit for the given block in bit map */ if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) { reiserfs_error(s, "vs-4080", "block %lu: bit already cleared", block); } apbi[nr].free_count++; journal_mark_dirty(th, bmbh); brelse(bmbh); reiserfs_prepare_for_journal(s, sbh, 1); /* update super block */ set_sb_free_blocks(rs, sb_free_blocks(rs) + 1); journal_mark_dirty(th, sbh); if (for_unformatted) { int depth = reiserfs_write_unlock_nested(s); dquot_free_block_nodirty(inode, 1); reiserfs_write_lock_nested(s, depth); } } void reiserfs_free_block(struct reiserfs_transaction_handle *th, struct inode *inode, b_blocknr_t block, int for_unformatted) { struct super_block *s = th->t_super; BUG_ON(!th->t_trans_id); RFALSE(!s, "vs-4061: trying to free block on nonexistent device"); if (!is_reusable(s, block, 1)) return; if (block > sb_block_count(REISERFS_SB(s)->s_rs)) { reiserfs_error(th->t_super, "bitmap-4072", "Trying to free block outside file system " "boundaries (%lu > %lu)", block, sb_block_count(REISERFS_SB(s)->s_rs)); return; } /* mark it before we clear it, just in case */ journal_mark_freed(th, s, block); _reiserfs_free_block(th, inode, block, for_unformatted); } /* preallocated blocks don't need to be run through journal_mark_freed */ static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th, struct inode *inode, b_blocknr_t block) { BUG_ON(!th->t_trans_id); RFALSE(!th->t_super, "vs-4060: trying to free block on nonexistent device"); if (!is_reusable(th->t_super, block, 1)) return; _reiserfs_free_block(th, inode, block, 1); } static void __discard_prealloc(struct reiserfs_transaction_handle *th, struct reiserfs_inode_info *ei) { unsigned long save = ei->i_prealloc_block; int dirty = 0; struct inode *inode = &ei->vfs_inode; BUG_ON(!th->t_trans_id); #ifdef CONFIG_REISERFS_CHECK if (ei->i_prealloc_count < 0) reiserfs_error(th->t_super, "zam-4001", "inode has negative prealloc blocks count."); #endif while (ei->i_prealloc_count > 0) { b_blocknr_t block_to_free; /* * reiserfs_free_prealloc_block can drop the write lock, * which could allow another caller to free the same block. * We can protect against it by modifying the prealloc * state before calling it. */ block_to_free = ei->i_prealloc_block++; ei->i_prealloc_count--; reiserfs_free_prealloc_block(th, inode, block_to_free); dirty = 1; } if (dirty) reiserfs_update_sd(th, inode); ei->i_prealloc_block = save; list_del_init(&ei->i_prealloc_list); } /* FIXME: It should be inline function */ void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th, struct inode *inode) { struct reiserfs_inode_info *ei = REISERFS_I(inode); BUG_ON(!th->t_trans_id); if (ei->i_prealloc_count) __discard_prealloc(th, ei); } void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th) { struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list; BUG_ON(!th->t_trans_id); while (!list_empty(plist)) { struct reiserfs_inode_info *ei; ei = list_entry(plist->next, struct reiserfs_inode_info, i_prealloc_list); #ifdef CONFIG_REISERFS_CHECK if (!ei->i_prealloc_count) { reiserfs_error(th->t_super, "zam-4001", "inode is in prealloc list but has " "no preallocated blocks."); } #endif __discard_prealloc(th, ei); } } void reiserfs_init_alloc_options(struct super_block *s) { set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s)); set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s)); set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s)); } /* block allocator related options are parsed here */ int reiserfs_parse_alloc_options(struct super_block *s, char *options) { char *this_char, *value; /* clear default settings */ REISERFS_SB(s)->s_alloc_options.bits = 0; while ((this_char = strsep(&options, ":")) != NULL) { if ((value = strchr(this_char, '=')) != NULL) *value++ = 0; if (!strcmp(this_char, "concentrating_formatted_nodes")) { int temp; SET_OPTION(concentrating_formatted_nodes); temp = (value && *value) ? simple_strtoul(value, &value, 0) : 10; if (temp <= 0 || temp > 100) { REISERFS_SB(s)->s_alloc_options.border = 10; } else { REISERFS_SB(s)->s_alloc_options.border = 100 / temp; } continue; } if (!strcmp(this_char, "displacing_large_files")) { SET_OPTION(displacing_large_files); REISERFS_SB(s)->s_alloc_options.large_file_size = (value && *value) ? simple_strtoul(value, &value, 0) : 16; continue; } if (!strcmp(this_char, "displacing_new_packing_localities")) { SET_OPTION(displacing_new_packing_localities); continue; } if (!strcmp(this_char, "old_hashed_relocation")) { SET_OPTION(old_hashed_relocation); continue; } if (!strcmp(this_char, "new_hashed_relocation")) { SET_OPTION(new_hashed_relocation); continue; } if (!strcmp(this_char, "dirid_groups")) { SET_OPTION(dirid_groups); continue; } if (!strcmp(this_char, "oid_groups")) { SET_OPTION(oid_groups); continue; } if (!strcmp(this_char, "packing_groups")) { SET_OPTION(packing_groups); continue; } if (!strcmp(this_char, "hashed_formatted_nodes")) { SET_OPTION(hashed_formatted_nodes); continue; } if (!strcmp(this_char, "skip_busy")) { SET_OPTION(skip_busy); continue; } if (!strcmp(this_char, "hundredth_slices")) { SET_OPTION(hundredth_slices); continue; } if (!strcmp(this_char, "old_way")) { SET_OPTION(old_way); continue; } if (!strcmp(this_char, "displace_based_on_dirid")) { SET_OPTION(displace_based_on_dirid); continue; } if (!strcmp(this_char, "preallocmin")) { REISERFS_SB(s)->s_alloc_options.preallocmin = (value && *value) ? simple_strtoul(value, &value, 0) : 4; continue; } if (!strcmp(this_char, "preallocsize")) { REISERFS_SB(s)->s_alloc_options.preallocsize = (value && *value) ? simple_strtoul(value, &value, 0) : PREALLOCATION_SIZE; continue; } reiserfs_warning(s, "zam-4001", "unknown option - %s", this_char); return 1; } reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s)); return 0; } static void print_sep(struct seq_file *seq, int *first) { if (!*first) seq_puts(seq, ":"); else *first = 0; } void show_alloc_options(struct seq_file *seq, struct super_block *s) { int first = 1; if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) | (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups))) return; seq_puts(seq, ",alloc="); if (TEST_OPTION(concentrating_formatted_nodes, s)) { print_sep(seq, &first); if (REISERFS_SB(s)->s_alloc_options.border != 10) { seq_printf(seq, "concentrating_formatted_nodes=%d", 100 / REISERFS_SB(s)->s_alloc_options.border); } else seq_puts(seq, "concentrating_formatted_nodes"); } if (TEST_OPTION(displacing_large_files, s)) { print_sep(seq, &first); if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) { seq_printf(seq, "displacing_large_files=%lu", REISERFS_SB(s)->s_alloc_options.large_file_size); } else seq_puts(seq, "displacing_large_files"); } if (TEST_OPTION(displacing_new_packing_localities, s)) { print_sep(seq, &first); seq_puts(seq, "displacing_new_packing_localities"); } if (TEST_OPTION(old_hashed_relocation, s)) { print_sep(seq, &first); seq_puts(seq, "old_hashed_relocation"); } if (TEST_OPTION(new_hashed_relocation, s)) { print_sep(seq, &first); seq_puts(seq, "new_hashed_relocation"); } if (TEST_OPTION(dirid_groups, s)) { print_sep(seq, &first); seq_puts(seq, "dirid_groups"); } if (TEST_OPTION(oid_groups, s)) { print_sep(seq, &first); seq_puts(seq, "oid_groups"); } if (TEST_OPTION(packing_groups, s)) { print_sep(seq, &first); seq_puts(seq, "packing_groups"); } if (TEST_OPTION(hashed_formatted_nodes, s)) { print_sep(seq, &first); seq_puts(seq, "hashed_formatted_nodes"); } if (TEST_OPTION(skip_busy, s)) { print_sep(seq, &first); seq_puts(seq, "skip_busy"); } if (TEST_OPTION(hundredth_slices, s)) { print_sep(seq, &first); seq_puts(seq, "hundredth_slices"); } if (TEST_OPTION(old_way, s)) { print_sep(seq, &first); seq_puts(seq, "old_way"); } if (TEST_OPTION(displace_based_on_dirid, s)) { print_sep(seq, &first); seq_puts(seq, "displace_based_on_dirid"); } if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) { print_sep(seq, &first); seq_printf(seq, "preallocmin=%d", REISERFS_SB(s)->s_alloc_options.preallocmin); } if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) { print_sep(seq, &first); seq_printf(seq, "preallocsize=%d", REISERFS_SB(s)->s_alloc_options.preallocsize); } } static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint) { char *hash_in; if (hint->formatted_node) { hash_in = (char *)&hint->key.k_dir_id; } else { if (!hint->inode) { /*hint->search_start = hint->beg;*/ hash_in = (char *)&hint->key.k_dir_id; } else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); else hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid); } hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); } /* * Relocation based on dirid, hashing them into a given bitmap block * files. Formatted nodes are unaffected, a separate policy covers them */ static void dirid_groups(reiserfs_blocknr_hint_t * hint) { unsigned long hash; __u32 dirid = 0; int bm = 0; struct super_block *sb = hint->th->t_super; if (hint->inode) dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); else if (hint->formatted_node) dirid = hint->key.k_dir_id; if (dirid) { bm = bmap_hash_id(sb, dirid); hash = bm * (sb->s_blocksize << 3); /* give a portion of the block group to metadata */ if (hint->inode) hash += sb->s_blocksize / 2; hint->search_start = hash; } } /* * Relocation based on oid, hashing them into a given bitmap block * files. Formatted nodes are unaffected, a separate policy covers them */ static void oid_groups(reiserfs_blocknr_hint_t * hint) { if (hint->inode) { unsigned long hash; __u32 oid; __u32 dirid; int bm; dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id); /* * keep the root dir and it's first set of subdirs close to * the start of the disk */ if (dirid <= 2) hash = (hint->inode->i_sb->s_blocksize << 3); else { oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid); bm = bmap_hash_id(hint->inode->i_sb, oid); hash = bm * (hint->inode->i_sb->s_blocksize << 3); } hint->search_start = hash; } } /* * returns 1 if it finds an indirect item and gets valid hint info * from it, otherwise 0 */ static int get_left_neighbor(reiserfs_blocknr_hint_t * hint) { struct treepath *path; struct buffer_head *bh; struct item_head *ih; int pos_in_item; __le32 *item; int ret = 0; /* * reiserfs code can call this function w/o pointer to path * structure supplied; then we rely on supplied search_start */ if (!hint->path) return 0; path = hint->path; bh = get_last_bh(path); RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor"); ih = tp_item_head(path); pos_in_item = path->pos_in_item; item = tp_item_body(path); hint->search_start = bh->b_blocknr; /* * for indirect item: go to left and look for the first non-hole entry * in the indirect item */ if (!hint->formatted_node && is_indirect_le_ih(ih)) { if (pos_in_item == I_UNFM_NUM(ih)) pos_in_item--; while (pos_in_item >= 0) { int t = get_block_num(item, pos_in_item); if (t) { hint->search_start = t; ret = 1; break; } pos_in_item--; } } /* does result value fit into specified region? */ return ret; } /* * should be, if formatted node, then try to put on first part of the device * specified as number of percent with mount option device, else try to put * on last of device. This is not to say it is good code to do so, * but the effect should be measured. */ static inline void set_border_in_hint(struct super_block *s, reiserfs_blocknr_hint_t * hint) { b_blocknr_t border = SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border; if (hint->formatted_node) hint->end = border - 1; else hint->beg = border; } static inline void displace_large_file(reiserfs_blocknr_hint_t * hint) { if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id), 4) % (hint->end - hint->beg); else hint->search_start = hint->beg + keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid), 4) % (hint->end - hint->beg); } static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint) { char *hash_in; if (!hint->inode) hash_in = (char *)&hint->key.k_dir_id; else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super)) hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id); else hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid); hint->search_start = hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg); } static inline int this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t * hint) { return hint->block == REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size; } #ifdef DISPLACE_NEW_PACKING_LOCALITIES static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint) { struct in_core_key *key = &hint->key; hint->th->displace_new_blocks = 0; hint->search_start = hint->beg + keyed_hash((char *)(&key->k_objectid), 4) % (hint->end - hint->beg); } #endif static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint) { b_blocknr_t border; u32 hash_in; if (hint->formatted_node || hint->inode == NULL) { return 0; } hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id); border = hint->beg + (u32) keyed_hash(((char *)(&hash_in)), 4) % (hint->end - hint->beg - 1); if (border > hint->search_start) hint->search_start = border; return 1; } static inline int old_way(reiserfs_blocknr_hint_t * hint) { b_blocknr_t border; if (hint->formatted_node || hint->inode == NULL) { return 0; } border = hint->beg + le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end - hint->beg); if (border > hint->search_start) hint->search_start = border; return 1; } static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint) { struct in_core_key *key = &hint->key; b_blocknr_t slice_start; slice_start = (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100); if (slice_start > hint->search_start || slice_start + (hint->end / 100) <= hint->search_start) { hint->search_start = slice_start; } } static void determine_search_start(reiserfs_blocknr_hint_t * hint, int amount_needed) { struct super_block *s = hint->th->t_super; int unfm_hint; hint->beg = 0; hint->end = SB_BLOCK_COUNT(s) - 1; /* This is former border algorithm. Now with tunable border offset */ if (concentrating_formatted_nodes(s)) set_border_in_hint(s, hint); #ifdef DISPLACE_NEW_PACKING_LOCALITIES /* * whenever we create a new directory, we displace it. At first * we will hash for location, later we might look for a moderately * empty place for it */ if (displacing_new_packing_localities(s) && hint->th->displace_new_blocks) { displace_new_packing_locality(hint); /* * we do not continue determine_search_start, * if new packing locality is being displaced */ return; } #endif /* * all persons should feel encouraged to add more special cases * here and test them */ if (displacing_large_files(s) && !hint->formatted_node && this_blocknr_allocation_would_make_it_a_large_file(hint)) { displace_large_file(hint); return; } /* * if none of our special cases is relevant, use the left * neighbor in the tree order of the new node we are allocating for */ if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) { hash_formatted_node(hint); return; } unfm_hint = get_left_neighbor(hint); /* * Mimic old block allocator behaviour, that is if VFS allowed for * preallocation, new blocks are displaced based on directory ID. * Also, if suggested search_start is less than last preallocated * block, we start searching from it, assuming that HDD dataflow * is faster in forward direction */ if (TEST_OPTION(old_way, s)) { if (!hint->formatted_node) { if (!reiserfs_hashed_relocation(s)) old_way(hint); else if (!reiserfs_no_unhashed_relocation(s)) old_hashed_relocation(hint); if (hint->inode && hint->search_start < REISERFS_I(hint->inode)->i_prealloc_block) hint->search_start = REISERFS_I(hint->inode)->i_prealloc_block; } return; } /* This is an approach proposed by Hans */ if (TEST_OPTION(hundredth_slices, s) && !(displacing_large_files(s) && !hint->formatted_node)) { hundredth_slices(hint); return; } /* old_hashed_relocation only works on unformatted */ if (!unfm_hint && !hint->formatted_node && TEST_OPTION(old_hashed_relocation, s)) { old_hashed_relocation(hint); } /* new_hashed_relocation works with both formatted/unformatted nodes */ if ((!unfm_hint || hint->formatted_node) && TEST_OPTION(new_hashed_relocation, s)) { new_hashed_relocation(hint); } /* dirid grouping works only on unformatted nodes */ if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) { dirid_groups(hint); } #ifdef DISPLACE_NEW_PACKING_LOCALITIES if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) { dirid_groups(hint); } #endif /* oid grouping works only on unformatted nodes */ if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) { oid_groups(hint); } return; } static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint) { /* make minimum size a mount option and benchmark both ways */ /* we preallocate blocks only for regular files, specific size */ /* benchmark preallocating always and see what happens */ hint->prealloc_size = 0; if (!hint->formatted_node && hint->preallocate) { if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode) && hint->inode->i_size >= REISERFS_SB(hint->th->t_super)->s_alloc_options. preallocmin * hint->inode->i_sb->s_blocksize) hint->prealloc_size = REISERFS_SB(hint->th->t_super)->s_alloc_options. preallocsize - 1; } return CARRY_ON; } static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, b_blocknr_t start, b_blocknr_t finish, int min, int amount_needed, int prealloc_size) { int rest = amount_needed; int nr_allocated; while (rest > 0 && start <= finish) { nr_allocated = scan_bitmap(hint->th, &start, finish, min, rest + prealloc_size, !hint->formatted_node, hint->block); if (nr_allocated == 0) /* no new blocks allocated, return */ break; /* fill free_blocknrs array first */ while (rest > 0 && nr_allocated > 0) { *new_blocknrs++ = start++; rest--; nr_allocated--; } /* do we have something to fill prealloc. array also ? */ if (nr_allocated > 0) { /* * it means prealloc_size was greater that 0 and * we do preallocation */ list_add(&REISERFS_I(hint->inode)->i_prealloc_list, &SB_JOURNAL(hint->th->t_super)-> j_prealloc_list); REISERFS_I(hint->inode)->i_prealloc_block = start; REISERFS_I(hint->inode)->i_prealloc_count = nr_allocated; break; } } return (amount_needed - rest); } static inline int blocknrs_and_prealloc_arrays_from_search_start (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, int amount_needed) { struct super_block *s = hint->th->t_super; b_blocknr_t start = hint->search_start; b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1; int passno = 0; int nr_allocated = 0; int depth; determine_prealloc_size(hint); if (!hint->formatted_node) { int quota_ret; #ifdef REISERQUOTA_DEBUG reiserfs_debug(s, REISERFS_DEBUG_CODE, "reiserquota: allocating %d blocks id=%u", amount_needed, hint->inode->i_uid); #endif depth = reiserfs_write_unlock_nested(s); quota_ret = dquot_alloc_block_nodirty(hint->inode, amount_needed); if (quota_ret) { /* Quota exceeded? */ reiserfs_write_lock_nested(s, depth); return QUOTA_EXCEEDED; } if (hint->preallocate && hint->prealloc_size) { #ifdef REISERQUOTA_DEBUG reiserfs_debug(s, REISERFS_DEBUG_CODE, "reiserquota: allocating (prealloc) %d blocks id=%u", hint->prealloc_size, hint->inode->i_uid); #endif quota_ret = dquot_prealloc_block_nodirty(hint->inode, hint->prealloc_size); if (quota_ret) hint->preallocate = hint->prealloc_size = 0; } /* for unformatted nodes, force large allocations */ reiserfs_write_lock_nested(s, depth); } do { switch (passno++) { case 0: /* Search from hint->search_start to end of disk */ start = hint->search_start; finish = SB_BLOCK_COUNT(s) - 1; break; case 1: /* Search from hint->beg to hint->search_start */ start = hint->beg; finish = hint->search_start; break; case 2: /* Last chance: Search from 0 to hint->beg */ start = 0; finish = hint->beg; break; default: /* We've tried searching everywhere, not enough space */ /* Free the blocks */ if (!hint->formatted_node) { #ifdef REISERQUOTA_DEBUG reiserfs_debug(s, REISERFS_DEBUG_CODE, "reiserquota: freeing (nospace) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated, hint->inode->i_uid); #endif /* Free not allocated blocks */ depth = reiserfs_write_unlock_nested(s); dquot_free_block_nodirty(hint->inode, amount_needed + hint->prealloc_size - nr_allocated); reiserfs_write_lock_nested(s, depth); } while (nr_allocated--) reiserfs_free_block(hint->th, hint->inode, new_blocknrs[nr_allocated], !hint->formatted_node); return NO_DISK_SPACE; } } while ((nr_allocated += allocate_without_wrapping_disk(hint, new_blocknrs + nr_allocated, start, finish, 1, amount_needed - nr_allocated, hint-> prealloc_size)) < amount_needed); if (!hint->formatted_node && amount_needed + hint->prealloc_size > nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) { /* Some of preallocation blocks were not allocated */ #ifdef REISERQUOTA_DEBUG reiserfs_debug(s, REISERFS_DEBUG_CODE, "reiserquota: freeing (failed prealloc) %d blocks id=%u", amount_needed + hint->prealloc_size - nr_allocated - REISERFS_I(hint->inode)->i_prealloc_count, hint->inode->i_uid); #endif depth = reiserfs_write_unlock_nested(s); dquot_free_block_nodirty(hint->inode, amount_needed + hint->prealloc_size - nr_allocated - REISERFS_I(hint->inode)-> i_prealloc_count); reiserfs_write_lock_nested(s, depth); } return CARRY_ON; } /* grab new blocknrs from preallocated list */ /* return amount still needed after using them */ static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, int amount_needed) { struct inode *inode = hint->inode; if (REISERFS_I(inode)->i_prealloc_count > 0) { while (amount_needed) { *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++; REISERFS_I(inode)->i_prealloc_count--; amount_needed--; if (REISERFS_I(inode)->i_prealloc_count <= 0) { list_del(&REISERFS_I(inode)->i_prealloc_list); break; } } } /* return amount still needed after using preallocated blocks */ return amount_needed; } int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint, b_blocknr_t *new_blocknrs, int amount_needed, /* Amount of blocks we have already reserved */ int reserved_by_us) { int initial_amount_needed = amount_needed; int ret; struct super_block *s = hint->th->t_super; /* Check if there is enough space, taking into account reserved space */ if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks < amount_needed - reserved_by_us) return NO_DISK_SPACE; /* should this be if !hint->inode && hint->preallocate? */ /* do you mean hint->formatted_node can be removed ? - Zam */ /* * hint->formatted_node cannot be removed because we try to access * inode information here, and there is often no inode associated with * metadata allocations - green */ if (!hint->formatted_node && hint->preallocate) { amount_needed = use_preallocated_list_if_available (hint, new_blocknrs, amount_needed); /* * We have all the block numbers we need from the * prealloc list */ if (amount_needed == 0) return CARRY_ON; new_blocknrs += (initial_amount_needed - amount_needed); } /* find search start and save it in hint structure */ determine_search_start(hint, amount_needed); if (hint->search_start >= SB_BLOCK_COUNT(s)) hint->search_start = SB_BLOCK_COUNT(s) - 1; /* allocation itself; fill new_blocknrs and preallocation arrays */ ret = blocknrs_and_prealloc_arrays_from_search_start (hint, new_blocknrs, amount_needed); /* * We used prealloc. list to fill (partially) new_blocknrs array. * If final allocation fails we need to return blocks back to * prealloc. list or just free them. -- Zam (I chose second * variant) */ if (ret != CARRY_ON) { while (amount_needed++ < initial_amount_needed) { reiserfs_free_block(hint->th, hint->inode, *(--new_blocknrs), 1); } } return ret; } void reiserfs_cache_bitmap_metadata(struct super_block *sb, struct buffer_head *bh, struct reiserfs_bitmap_info *info) { unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size); /* The first bit must ALWAYS be 1 */ if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data)) reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is " "corrupted: first bit must be 1", bh->b_blocknr); info->free_count = 0; while (--cur >= (unsigned long *)bh->b_data) { /* 0 and ~0 are special, we can optimize for them */ if (*cur == 0) info->free_count += BITS_PER_LONG; else if (*cur != ~0L) /* A mix, investigate */ info->free_count += BITS_PER_LONG - hweight_long(*cur); } } struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb, unsigned int bitmap) { b_blocknr_t block = (sb->s_blocksize << 3) * bitmap; struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap; struct buffer_head *bh; /* * Way old format filesystems had the bitmaps packed up front. * I doubt there are any of these left, but just in case... */ if (unlikely(test_bit(REISERFS_OLD_FORMAT, &REISERFS_SB(sb)->s_properties))) block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap; else if (bitmap == 0) block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1; bh = sb_bread(sb, block); if (bh == NULL) reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) " "reading failed", __func__, block); else { if (buffer_locked(bh)) { int depth; PROC_INFO_INC(sb, scan_bitmap.wait); depth = reiserfs_write_unlock_nested(sb); __wait_on_buffer(bh); reiserfs_write_lock_nested(sb, depth); } BUG_ON(!buffer_uptodate(bh)); BUG_ON(atomic_read(&bh->b_count) == 0); if (info->free_count == UINT_MAX) reiserfs_cache_bitmap_metadata(sb, bh, info); } return bh; } int reiserfs_init_bitmap_cache(struct super_block *sb) { struct reiserfs_bitmap_info *bitmap; unsigned int bmap_nr = reiserfs_bmap_count(sb); bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap))); if (bitmap == NULL) return -ENOMEM; memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr); SB_AP_BITMAP(sb) = bitmap; return 0; } void reiserfs_free_bitmap_cache(struct super_block *sb) { if (SB_AP_BITMAP(sb)) { vfree(SB_AP_BITMAP(sb)); SB_AP_BITMAP(sb) = NULL; } }
Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with Cregit http://github.com/cregit/cregit
Version 2.0-RC1