2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
4 /* Reiserfs block (de)allocator, bitmap-based. */
6 #include <linux/time.h>
7 #include <linux/reiserfs_fs.h>
8 #include <linux/errno.h>
9 #include <linux/buffer_head.h>
10 #include <linux/kernel.h>
11 #include <linux/pagemap.h>
12 #include <linux/vmalloc.h>
13 #include <linux/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_info(s, "block allocator 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,
51 unsigned int *bmap_nr,
54 /* It is in the bitmap block number equal to the block
55 * number divided by the number of bits in a block. */
56 *bmap_nr = block >> (s->s_blocksize_bits + 3);
57 /* Within that bitmap block it is located at bit offset *offset. */
58 *offset = block & ((s->s_blocksize << 3) - 1);
61 int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value)
63 unsigned int bmap, offset;
64 unsigned int bmap_count = reiserfs_bmap_count(s);
66 if (block == 0 || block >= SB_BLOCK_COUNT(s)) {
68 "vs-4010: is_reusable: block number is out of range %lu (%u)",
69 block, SB_BLOCK_COUNT(s));
73 get_bit_address(s, block, &bmap, &offset);
75 /* Old format filesystem? Unlikely, but the bitmaps are all up front so
76 * we need to account for it. */
77 if (unlikely(test_bit(REISERFS_OLD_FORMAT,
78 &(REISERFS_SB(s)->s_properties)))) {
79 b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1;
81 block <= bmap1 + bmap_count) {
82 reiserfs_warning(s, "vs: 4019: is_reusable: "
83 "bitmap block %lu(%u) can't be freed or reused",
89 reiserfs_warning(s, "vs: 4020: is_reusable: "
90 "bitmap block %lu(%u) can't be freed or reused",
96 if (bmap >= bmap_count) {
98 "vs-4030: is_reusable: there is no so many bitmap blocks: "
99 "block=%lu, bitmap_nr=%u", block, bmap);
103 if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) {
105 "vs-4050: is_reusable: this is root block (%u), "
106 "it must be busy", SB_ROOT_BLOCK(s));
113 /* searches in journal structures for a given block number (bmap, off). If block
114 is found in reiserfs journal it suggests next free block candidate to test. */
115 static inline int is_block_in_journal(struct super_block *s, unsigned int bmap,
120 if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) {
121 if (tmp) { /* hint supplied */
123 PROC_INFO_INC(s, scan_bitmap.in_journal_hint);
125 (*next) = off + 1; /* inc offset to avoid looping. */
126 PROC_INFO_INC(s, scan_bitmap.in_journal_nohint);
128 PROC_INFO_INC(s, scan_bitmap.retry);
134 /* it searches for a window of zero bits with given minimum and maximum lengths in one bitmap
136 static int scan_bitmap_block(struct reiserfs_transaction_handle *th,
137 unsigned int bmap_n, int *beg, int boundary,
138 int min, int max, int unfm)
140 struct super_block *s = th->t_super;
141 struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n];
142 struct buffer_head *bh;
146 BUG_ON(!th->t_trans_id);
148 RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of "
149 "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1);
150 PROC_INFO_INC(s, scan_bitmap.bmap);
151 /* this is unclear and lacks comments, explain how journal bitmaps
152 work here for the reader. Convey a sense of the design here. What
154 /* - I mean `a window of zero bits' as in description of this function - Zam. */
157 reiserfs_warning(s, "NULL bitmap info pointer for bitmap %d",
162 bh = reiserfs_read_bitmap_block(s, bmap_n);
168 if (bi->free_count < min) {
170 return 0; // No free blocks in this bitmap
173 /* search for a first zero bit -- beggining of a window */
174 *beg = reiserfs_find_next_zero_le_bit
175 ((unsigned long *)(bh->b_data), boundary, *beg);
177 if (*beg + min > boundary) { /* search for a zero bit fails or the rest of bitmap block
178 * cannot contain a zero window of minimum size */
183 if (unfm && is_block_in_journal(s, bmap_n, *beg, beg))
185 /* first zero bit found; we check next bits */
186 for (end = *beg + 1;; end++) {
187 if (end >= *beg + max || end >= boundary
188 || reiserfs_test_le_bit(end, bh->b_data)) {
192 /* finding the other end of zero bit window requires looking into journal structures (in
193 * case of searching for free blocks for unformatted nodes) */
194 if (unfm && is_block_in_journal(s, bmap_n, end, &next))
198 /* now (*beg) points to beginning of zero bits window,
199 * (end) points to one bit after the window end */
200 if (end - *beg >= min) { /* it seems we have found window of proper size */
202 reiserfs_prepare_for_journal(s, bh, 1);
203 /* try to set all blocks used checking are they still free */
204 for (i = *beg; i < end; i++) {
205 /* It seems that we should not check in journal again. */
206 if (reiserfs_test_and_set_le_bit
208 /* bit was set by another process
209 * while we slept in prepare_for_journal() */
210 PROC_INFO_INC(s, scan_bitmap.stolen);
211 if (i >= *beg + min) { /* we can continue with smaller set of allocated blocks,
212 * if length of this set is more or equal to `min' */
216 /* otherwise we clear all bit were set ... */
218 reiserfs_test_and_clear_le_bit
220 reiserfs_restore_prepared_buffer(s, bh);
222 /* ... and search again in current block from beginning */
226 bi->free_count -= (end - *beg);
227 journal_mark_dirty(th, s, bh);
230 /* free block count calculation */
231 reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s),
233 PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
234 journal_mark_dirty(th, s, SB_BUFFER_WITH_SB(s));
243 static int bmap_hash_id(struct super_block *s, u32 id)
245 char *hash_in = NULL;
252 hash_in = (char *)(&id);
253 hash = keyed_hash(hash_in, 4);
254 bm = hash % reiserfs_bmap_count(s);
258 /* this can only be true when SB_BMAP_NR = 1 */
259 if (bm >= reiserfs_bmap_count(s))
265 * hashes the id and then returns > 0 if the block group for the
266 * corresponding hash is full
268 static inline int block_group_used(struct super_block *s, u32 id)
270 int bm = bmap_hash_id(s, id);
271 struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm];
273 /* If we don't have cached information on this bitmap block, we're
274 * going to have to load it later anyway. Loading it here allows us
275 * to make a better decision. This favors long-term performance gain
276 * with a better on-disk layout vs. a short term gain of skipping the
277 * read and potentially having a bad placement. */
278 if (info->free_count == UINT_MAX) {
279 struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm);
283 if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) {
290 * the packing is returned in disk byte order
292 __le32 reiserfs_choose_packing(struct inode * dir)
295 if (TEST_OPTION(packing_groups, dir->i_sb)) {
296 u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
298 * some versions of reiserfsck expect packing locality 1 to be
301 if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir))
302 packing = INODE_PKEY(dir)->k_objectid;
304 packing = INODE_PKEY(dir)->k_dir_id;
306 packing = INODE_PKEY(dir)->k_objectid;
310 /* Tries to find contiguous zero bit window (given size) in given region of
311 * bitmap and place new blocks there. Returns number of allocated blocks. */
312 static int scan_bitmap(struct reiserfs_transaction_handle *th,
313 b_blocknr_t * start, b_blocknr_t finish,
314 int min, int max, int unfm, sector_t file_block)
316 int nr_allocated = 0;
317 struct super_block *s = th->t_super;
318 /* find every bm and bmap and bmap_nr in this file, and change them all to bitmap_blocknr
319 * - Hans, it is not a block number - Zam. */
321 unsigned int bm, off;
322 unsigned int end_bm, end_off;
323 unsigned int off_max = s->s_blocksize << 3;
325 BUG_ON(!th->t_trans_id);
327 PROC_INFO_INC(s, scan_bitmap.call);
328 if (SB_FREE_BLOCKS(s) <= 0)
329 return 0; // No point in looking for more free blocks
331 get_bit_address(s, *start, &bm, &off);
332 get_bit_address(s, finish, &end_bm, &end_off);
333 if (bm > reiserfs_bmap_count(s))
335 if (end_bm > reiserfs_bmap_count(s))
336 end_bm = reiserfs_bmap_count(s);
338 /* When the bitmap is more than 10% free, anyone can allocate.
339 * When it's less than 10% free, only files that already use the
340 * bitmap are allowed. Once we pass 80% full, this restriction
343 * We do this so that files that grow later still have space close to
344 * their original allocation. This improves locality, and presumably
345 * performance as a result.
347 * This is only an allocation policy and does not make up for getting a
348 * bad hint. Decent hinting must be implemented for this to work well.
350 if (TEST_OPTION(skip_busy, s)
351 && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) {
352 for (; bm < end_bm; bm++, off = 0) {
353 if ((off && (!unfm || (file_block != 0)))
354 || SB_AP_BITMAP(s)[bm].free_count >
355 (s->s_blocksize << 3) / 10)
357 scan_bitmap_block(th, bm, &off, off_max,
362 /* we know from above that start is a reasonable number */
363 get_bit_address(s, *start, &bm, &off);
366 for (; bm < end_bm; bm++, off = 0) {
368 scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
374 scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
377 *start = bm * off_max + off;
382 static void _reiserfs_free_block(struct reiserfs_transaction_handle *th,
383 struct inode *inode, b_blocknr_t block,
386 struct super_block *s = th->t_super;
387 struct reiserfs_super_block *rs;
388 struct buffer_head *sbh, *bmbh;
389 struct reiserfs_bitmap_info *apbi;
390 unsigned int nr, offset;
392 BUG_ON(!th->t_trans_id);
394 PROC_INFO_INC(s, free_block);
396 rs = SB_DISK_SUPER_BLOCK(s);
397 sbh = SB_BUFFER_WITH_SB(s);
398 apbi = SB_AP_BITMAP(s);
400 get_bit_address(s, block, &nr, &offset);
402 if (nr >= reiserfs_bmap_count(s)) {
403 reiserfs_warning(s, "vs-4075: reiserfs_free_block: "
404 "block %lu is out of range on %s "
405 "(nr=%u,max=%u)", block,
406 reiserfs_bdevname(s), nr,
407 reiserfs_bmap_count(s));
411 bmbh = reiserfs_read_bitmap_block(s, nr);
415 reiserfs_prepare_for_journal(s, bmbh, 1);
417 /* clear bit for the given block in bit map */
418 if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) {
419 reiserfs_warning(s, "vs-4080: reiserfs_free_block: "
420 "free_block (%s:%lu)[dev:blocknr]: bit already cleared",
421 reiserfs_bdevname(s), block);
423 apbi[nr].free_count++;
424 journal_mark_dirty(th, s, bmbh);
427 reiserfs_prepare_for_journal(s, sbh, 1);
428 /* update super block */
429 set_sb_free_blocks(rs, sb_free_blocks(rs) + 1);
431 journal_mark_dirty(th, s, sbh);
433 DQUOT_FREE_BLOCK_NODIRTY(inode, 1);
436 void reiserfs_free_block(struct reiserfs_transaction_handle *th,
437 struct inode *inode, b_blocknr_t block,
440 struct super_block *s = th->t_super;
441 BUG_ON(!th->t_trans_id);
443 RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
444 if (!is_reusable(s, block, 1))
447 if (block > sb_block_count(REISERFS_SB(s)->s_rs)) {
448 reiserfs_panic(th->t_super, "bitmap-4072",
449 "Trying to free block outside file system "
450 "boundaries (%lu > %lu)",
451 block, sb_block_count(REISERFS_SB(s)->s_rs));
454 /* mark it before we clear it, just in case */
455 journal_mark_freed(th, s, block);
456 _reiserfs_free_block(th, inode, block, for_unformatted);
459 /* preallocated blocks don't need to be run through journal_mark_freed */
460 static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th,
461 struct inode *inode, b_blocknr_t block)
463 BUG_ON(!th->t_trans_id);
465 "vs-4060: trying to free block on nonexistent device");
466 if (!is_reusable(th->t_super, block, 1))
468 _reiserfs_free_block(th, inode, block, 1);
471 static void __discard_prealloc(struct reiserfs_transaction_handle *th,
472 struct reiserfs_inode_info *ei)
474 unsigned long save = ei->i_prealloc_block;
476 struct inode *inode = &ei->vfs_inode;
477 BUG_ON(!th->t_trans_id);
478 #ifdef CONFIG_REISERFS_CHECK
479 if (ei->i_prealloc_count < 0)
480 reiserfs_warning(th->t_super,
481 "zam-4001:%s: inode has negative prealloc blocks count.",
484 while (ei->i_prealloc_count > 0) {
485 reiserfs_free_prealloc_block(th, inode, ei->i_prealloc_block);
486 ei->i_prealloc_block++;
487 ei->i_prealloc_count--;
491 reiserfs_update_sd(th, inode);
492 ei->i_prealloc_block = save;
493 list_del_init(&(ei->i_prealloc_list));
496 /* FIXME: It should be inline function */
497 void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th,
500 struct reiserfs_inode_info *ei = REISERFS_I(inode);
501 BUG_ON(!th->t_trans_id);
502 if (ei->i_prealloc_count)
503 __discard_prealloc(th, ei);
506 void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th)
508 struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
510 BUG_ON(!th->t_trans_id);
512 while (!list_empty(plist)) {
513 struct reiserfs_inode_info *ei;
514 ei = list_entry(plist->next, struct reiserfs_inode_info,
516 #ifdef CONFIG_REISERFS_CHECK
517 if (!ei->i_prealloc_count) {
518 reiserfs_warning(th->t_super,
519 "zam-4001:%s: inode is in prealloc list but has no preallocated blocks.",
523 __discard_prealloc(th, ei);
527 void reiserfs_init_alloc_options(struct super_block *s)
529 set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
530 set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
531 set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
534 /* block allocator related options are parsed here */
535 int reiserfs_parse_alloc_options(struct super_block *s, char *options)
537 char *this_char, *value;
539 REISERFS_SB(s)->s_alloc_options.bits = 0; /* clear default settings */
541 while ((this_char = strsep(&options, ":")) != NULL) {
542 if ((value = strchr(this_char, '=')) != NULL)
545 if (!strcmp(this_char, "concentrating_formatted_nodes")) {
547 SET_OPTION(concentrating_formatted_nodes);
549 && *value) ? simple_strtoul(value, &value,
551 if (temp <= 0 || temp > 100) {
552 REISERFS_SB(s)->s_alloc_options.border = 10;
554 REISERFS_SB(s)->s_alloc_options.border =
559 if (!strcmp(this_char, "displacing_large_files")) {
560 SET_OPTION(displacing_large_files);
561 REISERFS_SB(s)->s_alloc_options.large_file_size =
563 && *value) ? simple_strtoul(value, &value, 0) : 16;
566 if (!strcmp(this_char, "displacing_new_packing_localities")) {
567 SET_OPTION(displacing_new_packing_localities);
571 if (!strcmp(this_char, "old_hashed_relocation")) {
572 SET_OPTION(old_hashed_relocation);
576 if (!strcmp(this_char, "new_hashed_relocation")) {
577 SET_OPTION(new_hashed_relocation);
581 if (!strcmp(this_char, "dirid_groups")) {
582 SET_OPTION(dirid_groups);
585 if (!strcmp(this_char, "oid_groups")) {
586 SET_OPTION(oid_groups);
589 if (!strcmp(this_char, "packing_groups")) {
590 SET_OPTION(packing_groups);
593 if (!strcmp(this_char, "hashed_formatted_nodes")) {
594 SET_OPTION(hashed_formatted_nodes);
598 if (!strcmp(this_char, "skip_busy")) {
599 SET_OPTION(skip_busy);
603 if (!strcmp(this_char, "hundredth_slices")) {
604 SET_OPTION(hundredth_slices);
608 if (!strcmp(this_char, "old_way")) {
613 if (!strcmp(this_char, "displace_based_on_dirid")) {
614 SET_OPTION(displace_based_on_dirid);
618 if (!strcmp(this_char, "preallocmin")) {
619 REISERFS_SB(s)->s_alloc_options.preallocmin =
621 && *value) ? simple_strtoul(value, &value, 0) : 4;
625 if (!strcmp(this_char, "preallocsize")) {
626 REISERFS_SB(s)->s_alloc_options.preallocsize =
628 && *value) ? simple_strtoul(value, &value,
634 reiserfs_warning(s, "zam-4001: %s : unknown option - %s",
635 __func__, this_char);
639 reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
643 static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint)
646 if (hint->formatted_node) {
647 hash_in = (char *)&hint->key.k_dir_id;
650 //hint->search_start = hint->beg;
651 hash_in = (char *)&hint->key.k_dir_id;
653 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
654 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
657 (char *)(&INODE_PKEY(hint->inode)->k_objectid);
661 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
665 * Relocation based on dirid, hashing them into a given bitmap block
666 * files. Formatted nodes are unaffected, a separate policy covers them
668 static void dirid_groups(reiserfs_blocknr_hint_t * hint)
673 struct super_block *sb = hint->th->t_super;
675 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
676 else if (hint->formatted_node)
677 dirid = hint->key.k_dir_id;
680 bm = bmap_hash_id(sb, dirid);
681 hash = bm * (sb->s_blocksize << 3);
682 /* give a portion of the block group to metadata */
684 hash += sb->s_blocksize / 2;
685 hint->search_start = hash;
690 * Relocation based on oid, hashing them into a given bitmap block
691 * files. Formatted nodes are unaffected, a separate policy covers them
693 static void oid_groups(reiserfs_blocknr_hint_t * hint)
701 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
703 /* keep the root dir and it's first set of subdirs close to
704 * the start of the disk
707 hash = (hint->inode->i_sb->s_blocksize << 3);
709 oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
710 bm = bmap_hash_id(hint->inode->i_sb, oid);
711 hash = bm * (hint->inode->i_sb->s_blocksize << 3);
713 hint->search_start = hash;
717 /* returns 1 if it finds an indirect item and gets valid hint info
718 * from it, otherwise 0
720 static int get_left_neighbor(reiserfs_blocknr_hint_t * hint)
722 struct treepath *path;
723 struct buffer_head *bh;
724 struct item_head *ih;
729 if (!hint->path) /* reiserfs code can call this function w/o pointer to path
730 * structure supplied; then we rely on supplied search_start */
734 bh = get_last_bh(path);
735 RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor");
737 pos_in_item = path->pos_in_item;
738 item = get_item(path);
740 hint->search_start = bh->b_blocknr;
742 if (!hint->formatted_node && is_indirect_le_ih(ih)) {
743 /* for indirect item: go to left and look for the first non-hole entry
744 in the indirect item */
745 if (pos_in_item == I_UNFM_NUM(ih))
747 // pos_in_item = I_UNFM_NUM (ih) - 1;
748 while (pos_in_item >= 0) {
749 int t = get_block_num(item, pos_in_item);
751 hint->search_start = t;
759 /* does result value fit into specified region? */
763 /* should be, if formatted node, then try to put on first part of the device
764 specified as number of percent with mount option device, else try to put
765 on last of device. This is not to say it is good code to do so,
766 but the effect should be measured. */
767 static inline void set_border_in_hint(struct super_block *s,
768 reiserfs_blocknr_hint_t * hint)
771 SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
773 if (hint->formatted_node)
774 hint->end = border - 1;
779 static inline void displace_large_file(reiserfs_blocknr_hint_t * hint)
781 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
784 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id),
785 4) % (hint->end - hint->beg);
789 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid),
790 4) % (hint->end - hint->beg);
793 static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint)
798 hash_in = (char *)&hint->key.k_dir_id;
799 else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
800 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
802 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
805 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
809 this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *
812 return hint->block ==
813 REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
816 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
817 static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint)
819 struct in_core_key *key = &hint->key;
821 hint->th->displace_new_blocks = 0;
823 hint->beg + keyed_hash((char *)(&key->k_objectid),
824 4) % (hint->end - hint->beg);
828 static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint)
833 if (hint->formatted_node || hint->inode == NULL) {
837 hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
839 hint->beg + (u32) keyed_hash(((char *)(&hash_in)),
840 4) % (hint->end - hint->beg - 1);
841 if (border > hint->search_start)
842 hint->search_start = border;
847 static inline int old_way(reiserfs_blocknr_hint_t * hint)
851 if (hint->formatted_node || hint->inode == NULL) {
857 le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end -
859 if (border > hint->search_start)
860 hint->search_start = border;
865 static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint)
867 struct in_core_key *key = &hint->key;
868 b_blocknr_t slice_start;
871 (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100);
872 if (slice_start > hint->search_start
873 || slice_start + (hint->end / 100) <= hint->search_start) {
874 hint->search_start = slice_start;
878 static void determine_search_start(reiserfs_blocknr_hint_t * hint,
881 struct super_block *s = hint->th->t_super;
885 hint->end = SB_BLOCK_COUNT(s) - 1;
887 /* This is former border algorithm. Now with tunable border offset */
888 if (concentrating_formatted_nodes(s))
889 set_border_in_hint(s, hint);
891 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
892 /* whenever we create a new directory, we displace it. At first we will
893 hash for location, later we might look for a moderately empty place for
895 if (displacing_new_packing_localities(s)
896 && hint->th->displace_new_blocks) {
897 displace_new_packing_locality(hint);
899 /* we do not continue determine_search_start,
900 * if new packing locality is being displaced */
905 /* all persons should feel encouraged to add more special cases here and
908 if (displacing_large_files(s) && !hint->formatted_node
909 && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
910 displace_large_file(hint);
914 /* if none of our special cases is relevant, use the left neighbor in the
915 tree order of the new node we are allocating for */
916 if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) {
917 hash_formatted_node(hint);
921 unfm_hint = get_left_neighbor(hint);
923 /* Mimic old block allocator behaviour, that is if VFS allowed for preallocation,
924 new blocks are displaced based on directory ID. Also, if suggested search_start
925 is less than last preallocated block, we start searching from it, assuming that
926 HDD dataflow is faster in forward direction */
927 if (TEST_OPTION(old_way, s)) {
928 if (!hint->formatted_node) {
929 if (!reiserfs_hashed_relocation(s))
931 else if (!reiserfs_no_unhashed_relocation(s))
932 old_hashed_relocation(hint);
935 && hint->search_start <
936 REISERFS_I(hint->inode)->i_prealloc_block)
938 REISERFS_I(hint->inode)->i_prealloc_block;
943 /* This is an approach proposed by Hans */
944 if (TEST_OPTION(hundredth_slices, s)
945 && !(displacing_large_files(s) && !hint->formatted_node)) {
946 hundredth_slices(hint);
950 /* old_hashed_relocation only works on unformatted */
951 if (!unfm_hint && !hint->formatted_node &&
952 TEST_OPTION(old_hashed_relocation, s)) {
953 old_hashed_relocation(hint);
955 /* new_hashed_relocation works with both formatted/unformatted nodes */
956 if ((!unfm_hint || hint->formatted_node) &&
957 TEST_OPTION(new_hashed_relocation, s)) {
958 new_hashed_relocation(hint);
960 /* dirid grouping works only on unformatted nodes */
961 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
964 #ifdef DISPLACE_NEW_PACKING_LOCALITIES
965 if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
970 /* oid grouping works only on unformatted nodes */
971 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) {
977 static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
979 /* make minimum size a mount option and benchmark both ways */
980 /* we preallocate blocks only for regular files, specific size */
981 /* benchmark preallocating always and see what happens */
983 hint->prealloc_size = 0;
985 if (!hint->formatted_node && hint->preallocate) {
986 if (S_ISREG(hint->inode->i_mode)
987 && hint->inode->i_size >=
988 REISERFS_SB(hint->th->t_super)->s_alloc_options.
989 preallocmin * hint->inode->i_sb->s_blocksize)
990 hint->prealloc_size =
991 REISERFS_SB(hint->th->t_super)->s_alloc_options.
997 /* XXX I know it could be merged with upper-level function;
998 but may be result function would be too complex. */
999 static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint,
1000 b_blocknr_t * new_blocknrs,
1002 b_blocknr_t finish, int min,
1006 int rest = amount_needed;
1009 while (rest > 0 && start <= finish) {
1010 nr_allocated = scan_bitmap(hint->th, &start, finish, min,
1011 rest + prealloc_size,
1012 !hint->formatted_node, hint->block);
1014 if (nr_allocated == 0) /* no new blocks allocated, return */
1017 /* fill free_blocknrs array first */
1018 while (rest > 0 && nr_allocated > 0) {
1019 *new_blocknrs++ = start++;
1024 /* do we have something to fill prealloc. array also ? */
1025 if (nr_allocated > 0) {
1026 /* it means prealloc_size was greater that 0 and we do preallocation */
1027 list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
1028 &SB_JOURNAL(hint->th->t_super)->
1030 REISERFS_I(hint->inode)->i_prealloc_block = start;
1031 REISERFS_I(hint->inode)->i_prealloc_count =
1037 return (amount_needed - rest);
1040 static inline int blocknrs_and_prealloc_arrays_from_search_start
1041 (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs,
1042 int amount_needed) {
1043 struct super_block *s = hint->th->t_super;
1044 b_blocknr_t start = hint->search_start;
1045 b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
1047 int nr_allocated = 0;
1049 determine_prealloc_size(hint);
1050 if (!hint->formatted_node) {
1052 #ifdef REISERQUOTA_DEBUG
1053 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1054 "reiserquota: allocating %d blocks id=%u",
1055 amount_needed, hint->inode->i_uid);
1058 DQUOT_ALLOC_BLOCK_NODIRTY(hint->inode, amount_needed);
1059 if (quota_ret) /* Quota exceeded? */
1060 return QUOTA_EXCEEDED;
1061 if (hint->preallocate && hint->prealloc_size) {
1062 #ifdef REISERQUOTA_DEBUG
1063 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1064 "reiserquota: allocating (prealloc) %d blocks id=%u",
1065 hint->prealloc_size, hint->inode->i_uid);
1068 DQUOT_PREALLOC_BLOCK_NODIRTY(hint->inode,
1069 hint->prealloc_size);
1071 hint->preallocate = hint->prealloc_size = 0;
1073 /* for unformatted nodes, force large allocations */
1078 case 0: /* Search from hint->search_start to end of disk */
1079 start = hint->search_start;
1080 finish = SB_BLOCK_COUNT(s) - 1;
1082 case 1: /* Search from hint->beg to hint->search_start */
1084 finish = hint->search_start;
1086 case 2: /* Last chance: Search from 0 to hint->beg */
1090 default: /* We've tried searching everywhere, not enough space */
1091 /* Free the blocks */
1092 if (!hint->formatted_node) {
1093 #ifdef REISERQUOTA_DEBUG
1094 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1095 "reiserquota: freeing (nospace) %d blocks id=%u",
1097 hint->prealloc_size -
1099 hint->inode->i_uid);
1101 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed + hint->prealloc_size - nr_allocated); /* Free not allocated blocks */
1103 while (nr_allocated--)
1104 reiserfs_free_block(hint->th, hint->inode,
1105 new_blocknrs[nr_allocated],
1106 !hint->formatted_node);
1108 return NO_DISK_SPACE;
1110 } while ((nr_allocated += allocate_without_wrapping_disk(hint,
1120 if (!hint->formatted_node &&
1121 amount_needed + hint->prealloc_size >
1122 nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
1123 /* Some of preallocation blocks were not allocated */
1124 #ifdef REISERQUOTA_DEBUG
1125 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1126 "reiserquota: freeing (failed prealloc) %d blocks id=%u",
1127 amount_needed + hint->prealloc_size -
1129 REISERFS_I(hint->inode)->i_prealloc_count,
1130 hint->inode->i_uid);
1132 DQUOT_FREE_BLOCK_NODIRTY(hint->inode, amount_needed +
1133 hint->prealloc_size - nr_allocated -
1134 REISERFS_I(hint->inode)->
1141 /* grab new blocknrs from preallocated list */
1142 /* return amount still needed after using them */
1143 static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint,
1144 b_blocknr_t * new_blocknrs,
1147 struct inode *inode = hint->inode;
1149 if (REISERFS_I(inode)->i_prealloc_count > 0) {
1150 while (amount_needed) {
1152 *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++;
1153 REISERFS_I(inode)->i_prealloc_count--;
1157 if (REISERFS_I(inode)->i_prealloc_count <= 0) {
1158 list_del(&REISERFS_I(inode)->i_prealloc_list);
1163 /* return amount still needed after using preallocated blocks */
1164 return amount_needed;
1167 int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs, int amount_needed, int reserved_by_us /* Amount of blocks we have
1168 already reserved */ )
1170 int initial_amount_needed = amount_needed;
1172 struct super_block *s = hint->th->t_super;
1174 /* Check if there is enough space, taking into account reserved space */
1175 if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks <
1176 amount_needed - reserved_by_us)
1177 return NO_DISK_SPACE;
1178 /* should this be if !hint->inode && hint->preallocate? */
1179 /* do you mean hint->formatted_node can be removed ? - Zam */
1180 /* hint->formatted_node cannot be removed because we try to access
1181 inode information here, and there is often no inode assotiated with
1182 metadata allocations - green */
1184 if (!hint->formatted_node && hint->preallocate) {
1185 amount_needed = use_preallocated_list_if_available
1186 (hint, new_blocknrs, amount_needed);
1187 if (amount_needed == 0) /* all blocknrs we need we got from
1190 new_blocknrs += (initial_amount_needed - amount_needed);
1193 /* find search start and save it in hint structure */
1194 determine_search_start(hint, amount_needed);
1195 if (hint->search_start >= SB_BLOCK_COUNT(s))
1196 hint->search_start = SB_BLOCK_COUNT(s) - 1;
1198 /* allocation itself; fill new_blocknrs and preallocation arrays */
1199 ret = blocknrs_and_prealloc_arrays_from_search_start
1200 (hint, new_blocknrs, amount_needed);
1202 /* we used prealloc. list to fill (partially) new_blocknrs array. If final allocation fails we
1203 * need to return blocks back to prealloc. list or just free them. -- Zam (I chose second
1206 if (ret != CARRY_ON) {
1207 while (amount_needed++ < initial_amount_needed) {
1208 reiserfs_free_block(hint->th, hint->inode,
1209 *(--new_blocknrs), 1);
1215 void reiserfs_cache_bitmap_metadata(struct super_block *sb,
1216 struct buffer_head *bh,
1217 struct reiserfs_bitmap_info *info)
1219 unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size);
1221 /* The first bit must ALWAYS be 1 */
1222 BUG_ON(!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data));
1224 info->free_count = 0;
1226 while (--cur >= (unsigned long *)bh->b_data) {
1229 /* 0 and ~0 are special, we can optimize for them */
1231 info->free_count += BITS_PER_LONG;
1232 else if (*cur != ~0L) /* A mix, investigate */
1233 for (i = BITS_PER_LONG - 1; i >= 0; i--)
1234 if (!reiserfs_test_le_bit(i, cur))
1239 struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb,
1240 unsigned int bitmap)
1242 b_blocknr_t block = (sb->s_blocksize << 3) * bitmap;
1243 struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap;
1244 struct buffer_head *bh;
1246 /* Way old format filesystems had the bitmaps packed up front.
1247 * I doubt there are any of these left, but just in case... */
1248 if (unlikely(test_bit(REISERFS_OLD_FORMAT,
1249 &(REISERFS_SB(sb)->s_properties))))
1250 block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap;
1251 else if (bitmap == 0)
1252 block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1;
1254 bh = sb_bread(sb, block);
1256 reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) "
1257 "reading failed", __func__, block);
1259 if (buffer_locked(bh)) {
1260 PROC_INFO_INC(sb, scan_bitmap.wait);
1261 __wait_on_buffer(bh);
1263 BUG_ON(!buffer_uptodate(bh));
1264 BUG_ON(atomic_read(&bh->b_count) == 0);
1266 if (info->free_count == UINT_MAX)
1267 reiserfs_cache_bitmap_metadata(sb, bh, info);
1273 int reiserfs_init_bitmap_cache(struct super_block *sb)
1275 struct reiserfs_bitmap_info *bitmap;
1276 unsigned int bmap_nr = reiserfs_bmap_count(sb);
1278 bitmap = vmalloc(sizeof(*bitmap) * bmap_nr);
1282 memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr);
1284 SB_AP_BITMAP(sb) = bitmap;
1289 void reiserfs_free_bitmap_cache(struct super_block *sb)
1291 if (SB_AP_BITMAP(sb)) {
1292 vfree(SB_AP_BITMAP(sb));
1293 SB_AP_BITMAP(sb) = NULL;