blob: bf708ac287b42b38196801514cf5ec1b9e82437b [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
3 */
4/* Reiserfs block (de)allocator, bitmap-based. */
5
Linus Torvalds1da177e2005-04-16 15:20:36 -07006#include <linux/time.h>
Al Virof466c6f2012-03-17 01:16:43 -04007#include "reiserfs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -07008#include <linux/errno.h>
9#include <linux/buffer_head.h>
10#include <linux/kernel.h>
11#include <linux/pagemap.h>
Jeff Mahoney6f010462006-09-30 23:28:43 -070012#include <linux/vmalloc.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/quotaops.h>
Jan Karac3aa0772011-12-21 20:17:10 +010014#include <linux/seq_file.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015
16#define PREALLOCATION_SIZE 9
17
18/* different reiserfs block allocator options */
19
20#define SB_ALLOC_OPTS(s) (REISERFS_SB(s)->s_alloc_options.bits)
21
22#define _ALLOC_concentrating_formatted_nodes 0
23#define _ALLOC_displacing_large_files 1
24#define _ALLOC_displacing_new_packing_localities 2
25#define _ALLOC_old_hashed_relocation 3
26#define _ALLOC_new_hashed_relocation 4
27#define _ALLOC_skip_busy 5
28#define _ALLOC_displace_based_on_dirid 6
29#define _ALLOC_hashed_formatted_nodes 7
30#define _ALLOC_old_way 8
31#define _ALLOC_hundredth_slices 9
32#define _ALLOC_dirid_groups 10
33#define _ALLOC_oid_groups 11
34#define _ALLOC_packing_groups 12
35
36#define concentrating_formatted_nodes(s) test_bit(_ALLOC_concentrating_formatted_nodes, &SB_ALLOC_OPTS(s))
37#define displacing_large_files(s) test_bit(_ALLOC_displacing_large_files, &SB_ALLOC_OPTS(s))
38#define displacing_new_packing_localities(s) test_bit(_ALLOC_displacing_new_packing_localities, &SB_ALLOC_OPTS(s))
39
40#define SET_OPTION(optname) \
41 do { \
Jeff Mahoney1d889d92009-03-30 14:02:20 -040042 reiserfs_info(s, "block allocator option \"%s\" is set", #optname); \
43 set_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s)); \
Linus Torvalds1da177e2005-04-16 15:20:36 -070044 } while(0)
45#define TEST_OPTION(optname, s) \
46 test_bit(_ALLOC_ ## optname , &SB_ALLOC_OPTS(s))
47
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070048static inline void get_bit_address(struct super_block *s,
Jeff Mahoney3ee16672007-10-18 23:39:25 -070049 b_blocknr_t block,
50 unsigned int *bmap_nr,
51 unsigned int *offset)
Linus Torvalds1da177e2005-04-16 15:20:36 -070052{
Jeff Mahoney098297b2014-04-23 10:00:36 -040053 /*
54 * It is in the bitmap block number equal to the block
55 * number divided by the number of bits in a block.
56 */
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070057 *bmap_nr = block >> (s->s_blocksize_bits + 3);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070058 /* Within that bitmap block it is located at bit offset *offset. */
59 *offset = block & ((s->s_blocksize << 3) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -070060}
61
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070062int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value)
Linus Torvalds1da177e2005-04-16 15:20:36 -070063{
Jeff Mahoney3ee16672007-10-18 23:39:25 -070064 unsigned int bmap, offset;
Jeff Mahoneycb680c12007-10-18 23:39:27 -070065 unsigned int bmap_count = reiserfs_bmap_count(s);
Linus Torvalds1da177e2005-04-16 15:20:36 -070066
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070067 if (block == 0 || block >= SB_BLOCK_COUNT(s)) {
Jeff Mahoney0030b642009-03-30 14:02:28 -040068 reiserfs_error(s, "vs-4010",
69 "block number is out of range %lu (%u)",
70 block, SB_BLOCK_COUNT(s));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070071 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -070072 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070073
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070074 get_bit_address(s, block, &bmap, &offset);
75
Jeff Mahoney098297b2014-04-23 10:00:36 -040076 /*
77 * Old format filesystem? Unlikely, but the bitmaps are all
78 * up front so we need to account for it.
79 */
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070080 if (unlikely(test_bit(REISERFS_OLD_FORMAT,
Jeff Mahoneya228bf82014-04-23 10:00:42 -040081 &REISERFS_SB(s)->s_properties))) {
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070082 b_blocknr_t bmap1 = REISERFS_SB(s)->s_sbh->b_blocknr + 1;
Jeff Mahoneycb680c12007-10-18 23:39:27 -070083 if (block >= bmap1 &&
84 block <= bmap1 + bmap_count) {
Jeff Mahoney0030b642009-03-30 14:02:28 -040085 reiserfs_error(s, "vs-4019", "bitmap block %lu(%u) "
86 "can't be freed or reused",
87 block, bmap_count);
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070088 return 0;
89 }
90 } else {
91 if (offset == 0) {
Jeff Mahoney0030b642009-03-30 14:02:28 -040092 reiserfs_error(s, "vs-4020", "bitmap block %lu(%u) "
93 "can't be freed or reused",
94 block, bmap_count);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -070095 return 0;
96 }
Jeff Mahoneye1fabd32006-09-30 23:28:40 -070097 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070098
Jeff Mahoneycb680c12007-10-18 23:39:27 -070099 if (bmap >= bmap_count) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400100 reiserfs_error(s, "vs-4030", "bitmap for requested block "
101 "is out of range: block=%lu, bitmap_nr=%u",
102 block, bmap);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700103 return 0;
104 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700106 if (bit_value == 0 && block == SB_ROOT_BLOCK(s)) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400107 reiserfs_error(s, "vs-4050", "this is root block (%u), "
108 "it must be busy", SB_ROOT_BLOCK(s));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700109 return 0;
110 }
111
112 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114
Jeff Mahoney098297b2014-04-23 10:00:36 -0400115/*
116 * Searches in journal structures for a given block number (bmap, off).
117 * If block is found in reiserfs journal it suggests next free block
118 * candidate to test.
119 */
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700120static inline int is_block_in_journal(struct super_block *s, unsigned int bmap,
121 int off, int *next)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700123 b_blocknr_t tmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700125 if (reiserfs_in_journal(s, bmap, off, 1, &tmp)) {
126 if (tmp) { /* hint supplied */
127 *next = tmp;
128 PROC_INFO_INC(s, scan_bitmap.in_journal_hint);
129 } else {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400130 (*next) = off + 1; /* inc offset to avoid looping. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700131 PROC_INFO_INC(s, scan_bitmap.in_journal_nohint);
132 }
133 PROC_INFO_INC(s, scan_bitmap.retry);
134 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700135 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700136 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137}
138
Jeff Mahoney098297b2014-04-23 10:00:36 -0400139/*
140 * Searches for a window of zero bits with given minimum and maximum
141 * lengths in one bitmap block
142 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700143static int scan_bitmap_block(struct reiserfs_transaction_handle *th,
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700144 unsigned int bmap_n, int *beg, int boundary,
145 int min, int max, int unfm)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700147 struct super_block *s = th->t_super;
148 struct reiserfs_bitmap_info *bi = &SB_AP_BITMAP(s)[bmap_n];
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700149 struct buffer_head *bh;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700150 int end, next;
151 int org = *beg;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700153 BUG_ON(!th->t_trans_id);
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700154 RFALSE(bmap_n >= reiserfs_bmap_count(s), "Bitmap %u is out of "
155 "range (0..%u)", bmap_n, reiserfs_bmap_count(s) - 1);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700156 PROC_INFO_INC(s, scan_bitmap.bmap);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700158 if (!bi) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400159 reiserfs_error(s, "jdm-4055", "NULL bitmap info pointer "
160 "for bitmap %d", bmap_n);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700161 return 0;
162 }
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700163
Jeff Mahoney50652272006-09-30 23:28:44 -0700164 bh = reiserfs_read_bitmap_block(s, bmap_n);
165 if (bh == NULL)
166 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700168 while (1) {
Jeff Mahoneycf776a72014-04-23 10:00:41 -0400169cont:
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700170 if (bi->free_count < min) {
171 brelse(bh);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400172 return 0; /* No free blocks in this bitmap */
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700173 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174
Daniel Mack3ad2f3fb2010-02-03 08:01:28 +0800175 /* search for a first zero bit -- beginning of a window */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700176 *beg = reiserfs_find_next_zero_le_bit
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700177 ((unsigned long *)(bh->b_data), boundary, *beg);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700178
Jeff Mahoney098297b2014-04-23 10:00:36 -0400179 /*
180 * search for a zero bit fails or the rest of bitmap block
181 * cannot contain a zero window of minimum size
182 */
183 if (*beg + min > boundary) {
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700184 brelse(bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700185 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700187
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700188 if (unfm && is_block_in_journal(s, bmap_n, *beg, beg))
189 continue;
190 /* first zero bit found; we check next bits */
191 for (end = *beg + 1;; end++) {
192 if (end >= *beg + max || end >= boundary
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700193 || reiserfs_test_le_bit(end, bh->b_data)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700194 next = end;
195 break;
196 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400197
198 /*
199 * finding the other end of zero bit window requires
200 * looking into journal structures (in case of
201 * searching for free blocks for unformatted nodes)
202 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700203 if (unfm && is_block_in_journal(s, bmap_n, end, &next))
204 break;
205 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206
Jeff Mahoney098297b2014-04-23 10:00:36 -0400207 /*
208 * now (*beg) points to beginning of zero bits window,
209 * (end) points to one bit after the window end
210 */
211
212 /* found window of proper size */
213 if (end - *beg >= min) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700214 int i;
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700215 reiserfs_prepare_for_journal(s, bh, 1);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400216 /*
217 * try to set all blocks used checking are
218 * they still free
219 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700220 for (i = *beg; i < end; i++) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400221 /* Don't check in journal again. */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700222 if (reiserfs_test_and_set_le_bit
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700223 (i, bh->b_data)) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400224 /*
225 * bit was set by another process while
226 * we slept in prepare_for_journal()
227 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700228 PROC_INFO_INC(s, scan_bitmap.stolen);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400229
230 /*
231 * we can continue with smaller set
232 * of allocated blocks, if length of
233 * this set is more or equal to `min'
234 */
235 if (i >= *beg + min) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700236 end = i;
237 break;
238 }
Jeff Mahoney098297b2014-04-23 10:00:36 -0400239
240 /*
241 * otherwise we clear all bit
242 * were set ...
243 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700244 while (--i >= *beg)
Akinobu Mita0c2fd1bfb2011-07-25 17:13:37 -0700245 reiserfs_clear_le_bit
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700246 (i, bh->b_data);
247 reiserfs_restore_prepared_buffer(s, bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700248 *beg = org;
Jeff Mahoney098297b2014-04-23 10:00:36 -0400249
250 /*
251 * Search again in current block
252 * from beginning
253 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700254 goto cont;
255 }
256 }
257 bi->free_count -= (end - *beg);
Jeff Mahoney09f1b802014-04-23 10:00:39 -0400258 journal_mark_dirty(th, bh);
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700259 brelse(bh);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700260
261 /* free block count calculation */
262 reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s),
263 1);
264 PUT_SB_FREE_BLOCKS(s, SB_FREE_BLOCKS(s) - (end - *beg));
Jeff Mahoney09f1b802014-04-23 10:00:39 -0400265 journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700266
267 return end - (*beg);
268 } else {
269 *beg = next;
270 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272}
273
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700274static int bmap_hash_id(struct super_block *s, u32 id)
275{
276 char *hash_in = NULL;
277 unsigned long hash;
278 unsigned bm;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700280 if (id <= 2) {
281 bm = 1;
282 } else {
283 hash_in = (char *)(&id);
284 hash = keyed_hash(hash_in, 4);
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700285 bm = hash % reiserfs_bmap_count(s);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700286 if (!bm)
287 bm = 1;
288 }
289 /* this can only be true when SB_BMAP_NR = 1 */
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700290 if (bm >= reiserfs_bmap_count(s))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700291 bm = 0;
292 return bm;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293}
294
295/*
296 * hashes the id and then returns > 0 if the block group for the
297 * corresponding hash is full
298 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700299static inline int block_group_used(struct super_block *s, u32 id)
300{
Jeff Mahoney50652272006-09-30 23:28:44 -0700301 int bm = bmap_hash_id(s, id);
302 struct reiserfs_bitmap_info *info = &SB_AP_BITMAP(s)[bm];
303
Jeff Mahoney098297b2014-04-23 10:00:36 -0400304 /*
305 * If we don't have cached information on this bitmap block, we're
Jeff Mahoney50652272006-09-30 23:28:44 -0700306 * going to have to load it later anyway. Loading it here allows us
Joe Perchesc78bad12008-02-03 17:33:42 +0200307 * to make a better decision. This favors long-term performance gain
Jeff Mahoney50652272006-09-30 23:28:44 -0700308 * with a better on-disk layout vs. a short term gain of skipping the
Jeff Mahoney098297b2014-04-23 10:00:36 -0400309 * read and potentially having a bad placement.
310 */
Jeff Mahoney4d208512007-10-18 23:39:26 -0700311 if (info->free_count == UINT_MAX) {
Jeff Mahoney50652272006-09-30 23:28:44 -0700312 struct buffer_head *bh = reiserfs_read_bitmap_block(s, bm);
313 brelse(bh);
314 }
315
316 if (info->free_count > ((s->s_blocksize << 3) * 60 / 100)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700317 return 0;
318 }
319 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700320}
321
322/*
323 * the packing is returned in disk byte order
324 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700325__le32 reiserfs_choose_packing(struct inode * dir)
Al Viro3e8962b2005-05-01 08:59:18 -0700326{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700327 __le32 packing;
328 if (TEST_OPTION(packing_groups, dir->i_sb)) {
329 u32 parent_dir = le32_to_cpu(INODE_PKEY(dir)->k_dir_id);
330 /*
331 * some versions of reiserfsck expect packing locality 1 to be
332 * special
333 */
334 if (parent_dir == 1 || block_group_used(dir->i_sb, parent_dir))
335 packing = INODE_PKEY(dir)->k_objectid;
336 else
337 packing = INODE_PKEY(dir)->k_dir_id;
338 } else
339 packing = INODE_PKEY(dir)->k_objectid;
340 return packing;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341}
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700342
Jeff Mahoney098297b2014-04-23 10:00:36 -0400343/*
344 * Tries to find contiguous zero bit window (given size) in given region of
345 * bitmap and place new blocks there. Returns number of allocated blocks.
346 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700347static int scan_bitmap(struct reiserfs_transaction_handle *th,
348 b_blocknr_t * start, b_blocknr_t finish,
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700349 int min, int max, int unfm, sector_t file_block)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700351 int nr_allocated = 0;
352 struct super_block *s = th->t_super;
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700353 unsigned int bm, off;
354 unsigned int end_bm, end_off;
355 unsigned int off_max = s->s_blocksize << 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700357 BUG_ON(!th->t_trans_id);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700358 PROC_INFO_INC(s, scan_bitmap.call);
Jeff Mahoney098297b2014-04-23 10:00:36 -0400359
360 /* No point in looking for more free blocks */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700361 if (SB_FREE_BLOCKS(s) <= 0)
Jeff Mahoney098297b2014-04-23 10:00:36 -0400362 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700364 get_bit_address(s, *start, &bm, &off);
365 get_bit_address(s, finish, &end_bm, &end_off);
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700366 if (bm > reiserfs_bmap_count(s))
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700367 return 0;
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700368 if (end_bm > reiserfs_bmap_count(s))
369 end_bm = reiserfs_bmap_count(s);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370
Jeff Mahoney098297b2014-04-23 10:00:36 -0400371 /*
372 * When the bitmap is more than 10% free, anyone can allocate.
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700373 * When it's less than 10% free, only files that already use the
374 * bitmap are allowed. Once we pass 80% full, this restriction
375 * is lifted.
376 *
377 * We do this so that files that grow later still have space close to
378 * their original allocation. This improves locality, and presumably
379 * performance as a result.
380 *
381 * This is only an allocation policy and does not make up for getting a
382 * bad hint. Decent hinting must be implemented for this to work well.
383 */
384 if (TEST_OPTION(skip_busy, s)
385 && SB_FREE_BLOCKS(s) > SB_BLOCK_COUNT(s) / 20) {
386 for (; bm < end_bm; bm++, off = 0) {
387 if ((off && (!unfm || (file_block != 0)))
388 || SB_AP_BITMAP(s)[bm].free_count >
389 (s->s_blocksize << 3) / 10)
390 nr_allocated =
391 scan_bitmap_block(th, bm, &off, off_max,
392 min, max, unfm);
393 if (nr_allocated)
394 goto ret;
395 }
396 /* we know from above that start is a reasonable number */
397 get_bit_address(s, *start, &bm, &off);
398 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700400 for (; bm < end_bm; bm++, off = 0) {
401 nr_allocated =
402 scan_bitmap_block(th, bm, &off, off_max, min, max, unfm);
403 if (nr_allocated)
404 goto ret;
405 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700407 nr_allocated =
408 scan_bitmap_block(th, bm, &off, end_off + 1, min, max, unfm);
409
Jeff Mahoneycf776a72014-04-23 10:00:41 -0400410ret:
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700411 *start = bm * off_max + off;
412 return nr_allocated;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413
414}
415
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700416static void _reiserfs_free_block(struct reiserfs_transaction_handle *th,
417 struct inode *inode, b_blocknr_t block,
418 int for_unformatted)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700420 struct super_block *s = th->t_super;
421 struct reiserfs_super_block *rs;
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700422 struct buffer_head *sbh, *bmbh;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700423 struct reiserfs_bitmap_info *apbi;
Jeff Mahoney3ee16672007-10-18 23:39:25 -0700424 unsigned int nr, offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700426 BUG_ON(!th->t_trans_id);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700427 PROC_INFO_INC(s, free_block);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700428 rs = SB_DISK_SUPER_BLOCK(s);
429 sbh = SB_BUFFER_WITH_SB(s);
430 apbi = SB_AP_BITMAP(s);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700432 get_bit_address(s, block, &nr, &offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433
Jeff Mahoneycb680c12007-10-18 23:39:27 -0700434 if (nr >= reiserfs_bmap_count(s)) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400435 reiserfs_error(s, "vs-4075", "block %lu is out of range",
436 block);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700437 return;
438 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700439
Jeff Mahoney50652272006-09-30 23:28:44 -0700440 bmbh = reiserfs_read_bitmap_block(s, nr);
441 if (!bmbh)
442 return;
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700443
444 reiserfs_prepare_for_journal(s, bmbh, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700445
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700446 /* clear bit for the given block in bit map */
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700447 if (!reiserfs_test_and_clear_le_bit(offset, bmbh->b_data)) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400448 reiserfs_error(s, "vs-4080",
449 "block %lu: bit already cleared", block);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700450 }
451 apbi[nr].free_count++;
Jeff Mahoney09f1b802014-04-23 10:00:39 -0400452 journal_mark_dirty(th, bmbh);
Jeff Mahoney0b3dc172006-09-30 23:28:42 -0700453 brelse(bmbh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700454
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700455 reiserfs_prepare_for_journal(s, sbh, 1);
456 /* update super block */
457 set_sb_free_blocks(rs, sb_free_blocks(rs) + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458
Jeff Mahoney09f1b802014-04-23 10:00:39 -0400459 journal_mark_dirty(th, sbh);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -0400460 if (for_unformatted) {
461 int depth = reiserfs_write_unlock_nested(s);
Christoph Hellwig5dd40562010-03-03 09:05:00 -0500462 dquot_free_block_nodirty(inode, 1);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -0400463 reiserfs_write_lock_nested(s, depth);
464 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465}
466
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700467void reiserfs_free_block(struct reiserfs_transaction_handle *th,
468 struct inode *inode, b_blocknr_t block,
469 int for_unformatted)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700470{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700471 struct super_block *s = th->t_super;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700472
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700473 BUG_ON(!th->t_trans_id);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700474 RFALSE(!s, "vs-4061: trying to free block on nonexistent device");
Jeff Mahoneyd4c3d192007-10-18 23:39:24 -0700475 if (!is_reusable(s, block, 1))
476 return;
477
478 if (block > sb_block_count(REISERFS_SB(s)->s_rs)) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400479 reiserfs_error(th->t_super, "bitmap-4072",
Jeff Mahoneyd4c3d192007-10-18 23:39:24 -0700480 "Trying to free block outside file system "
481 "boundaries (%lu > %lu)",
482 block, sb_block_count(REISERFS_SB(s)->s_rs));
483 return;
484 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700485 /* mark it before we clear it, just in case */
486 journal_mark_freed(th, s, block);
487 _reiserfs_free_block(th, inode, block, for_unformatted);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700488}
489
490/* preallocated blocks don't need to be run through journal_mark_freed */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700491static void reiserfs_free_prealloc_block(struct reiserfs_transaction_handle *th,
492 struct inode *inode, b_blocknr_t block)
493{
Jeff Mahoneyd4c3d192007-10-18 23:39:24 -0700494 BUG_ON(!th->t_trans_id);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700495 RFALSE(!th->t_super,
496 "vs-4060: trying to free block on nonexistent device");
Jeff Mahoneyd4c3d192007-10-18 23:39:24 -0700497 if (!is_reusable(th->t_super, block, 1))
498 return;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700499 _reiserfs_free_block(th, inode, block, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700500}
501
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700502static void __discard_prealloc(struct reiserfs_transaction_handle *th,
503 struct reiserfs_inode_info *ei)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700505 unsigned long save = ei->i_prealloc_block;
506 int dirty = 0;
507 struct inode *inode = &ei->vfs_inode;
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700508
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700509 BUG_ON(!th->t_trans_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700511 if (ei->i_prealloc_count < 0)
Jeff Mahoney0030b642009-03-30 14:02:28 -0400512 reiserfs_error(th->t_super, "zam-4001",
513 "inode has negative prealloc blocks count.");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700515 while (ei->i_prealloc_count > 0) {
Jeff Mahoney08db1412017-06-22 16:47:34 -0400516 b_blocknr_t block_to_free;
517
518 /*
519 * reiserfs_free_prealloc_block can drop the write lock,
520 * which could allow another caller to free the same block.
521 * We can protect against it by modifying the prealloc
522 * state before calling it.
523 */
524 block_to_free = ei->i_prealloc_block++;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700525 ei->i_prealloc_count--;
Jeff Mahoney08db1412017-06-22 16:47:34 -0400526 reiserfs_free_prealloc_block(th, inode, block_to_free);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700527 dirty = 1;
528 }
529 if (dirty)
530 reiserfs_update_sd(th, inode);
531 ei->i_prealloc_block = save;
Jeff Mahoneya228bf82014-04-23 10:00:42 -0400532 list_del_init(&ei->i_prealloc_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533}
534
535/* FIXME: It should be inline function */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700536void reiserfs_discard_prealloc(struct reiserfs_transaction_handle *th,
537 struct inode *inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700538{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700539 struct reiserfs_inode_info *ei = REISERFS_I(inode);
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700540
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700541 BUG_ON(!th->t_trans_id);
542 if (ei->i_prealloc_count)
543 __discard_prealloc(th, ei);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544}
545
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700546void reiserfs_discard_all_prealloc(struct reiserfs_transaction_handle *th)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700548 struct list_head *plist = &SB_JOURNAL(th->t_super)->j_prealloc_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700550 BUG_ON(!th->t_trans_id);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700551 while (!list_empty(plist)) {
552 struct reiserfs_inode_info *ei;
553 ei = list_entry(plist->next, struct reiserfs_inode_info,
554 i_prealloc_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555#ifdef CONFIG_REISERFS_CHECK
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700556 if (!ei->i_prealloc_count) {
Jeff Mahoney0030b642009-03-30 14:02:28 -0400557 reiserfs_error(th->t_super, "zam-4001",
558 "inode is in prealloc list but has "
559 "no preallocated blocks.");
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700560 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561#endif
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700562 __discard_prealloc(th, ei);
563 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564}
565
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700566void reiserfs_init_alloc_options(struct super_block *s)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700568 set_bit(_ALLOC_skip_busy, &SB_ALLOC_OPTS(s));
569 set_bit(_ALLOC_dirid_groups, &SB_ALLOC_OPTS(s));
570 set_bit(_ALLOC_packing_groups, &SB_ALLOC_OPTS(s));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571}
572
573/* block allocator related options are parsed here */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700574int reiserfs_parse_alloc_options(struct super_block *s, char *options)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700576 char *this_char, *value;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
Jeff Mahoney098297b2014-04-23 10:00:36 -0400578 /* clear default settings */
579 REISERFS_SB(s)->s_alloc_options.bits = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700580
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700581 while ((this_char = strsep(&options, ":")) != NULL) {
582 if ((value = strchr(this_char, '=')) != NULL)
583 *value++ = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700585 if (!strcmp(this_char, "concentrating_formatted_nodes")) {
586 int temp;
587 SET_OPTION(concentrating_formatted_nodes);
588 temp = (value
589 && *value) ? simple_strtoul(value, &value,
590 0) : 10;
591 if (temp <= 0 || temp > 100) {
592 REISERFS_SB(s)->s_alloc_options.border = 10;
593 } else {
594 REISERFS_SB(s)->s_alloc_options.border =
595 100 / temp;
596 }
597 continue;
598 }
599 if (!strcmp(this_char, "displacing_large_files")) {
600 SET_OPTION(displacing_large_files);
601 REISERFS_SB(s)->s_alloc_options.large_file_size =
602 (value
603 && *value) ? simple_strtoul(value, &value, 0) : 16;
604 continue;
605 }
606 if (!strcmp(this_char, "displacing_new_packing_localities")) {
607 SET_OPTION(displacing_new_packing_localities);
608 continue;
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700609 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700611 if (!strcmp(this_char, "old_hashed_relocation")) {
612 SET_OPTION(old_hashed_relocation);
613 continue;
614 }
615
616 if (!strcmp(this_char, "new_hashed_relocation")) {
617 SET_OPTION(new_hashed_relocation);
618 continue;
619 }
620
621 if (!strcmp(this_char, "dirid_groups")) {
622 SET_OPTION(dirid_groups);
623 continue;
624 }
625 if (!strcmp(this_char, "oid_groups")) {
626 SET_OPTION(oid_groups);
627 continue;
628 }
629 if (!strcmp(this_char, "packing_groups")) {
630 SET_OPTION(packing_groups);
631 continue;
632 }
633 if (!strcmp(this_char, "hashed_formatted_nodes")) {
634 SET_OPTION(hashed_formatted_nodes);
635 continue;
636 }
637
638 if (!strcmp(this_char, "skip_busy")) {
639 SET_OPTION(skip_busy);
640 continue;
641 }
642
643 if (!strcmp(this_char, "hundredth_slices")) {
644 SET_OPTION(hundredth_slices);
645 continue;
646 }
647
648 if (!strcmp(this_char, "old_way")) {
649 SET_OPTION(old_way);
650 continue;
651 }
652
653 if (!strcmp(this_char, "displace_based_on_dirid")) {
654 SET_OPTION(displace_based_on_dirid);
655 continue;
656 }
657
658 if (!strcmp(this_char, "preallocmin")) {
659 REISERFS_SB(s)->s_alloc_options.preallocmin =
660 (value
661 && *value) ? simple_strtoul(value, &value, 0) : 4;
662 continue;
663 }
664
665 if (!strcmp(this_char, "preallocsize")) {
666 REISERFS_SB(s)->s_alloc_options.preallocsize =
667 (value
668 && *value) ? simple_strtoul(value, &value,
669 0) :
670 PREALLOCATION_SIZE;
671 continue;
672 }
673
Jeff Mahoney45b03d52009-03-30 14:02:21 -0400674 reiserfs_warning(s, "zam-4001", "unknown option - %s",
675 this_char);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700676 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677 }
678
Jeff Mahoney1d889d92009-03-30 14:02:20 -0400679 reiserfs_info(s, "allocator options = [%08x]\n", SB_ALLOC_OPTS(s));
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700680 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682
Jan Karac3aa0772011-12-21 20:17:10 +0100683static void print_sep(struct seq_file *seq, int *first)
684{
685 if (!*first)
686 seq_puts(seq, ":");
687 else
688 *first = 0;
689}
690
691void show_alloc_options(struct seq_file *seq, struct super_block *s)
692{
693 int first = 1;
694
695 if (SB_ALLOC_OPTS(s) == ((1 << _ALLOC_skip_busy) |
696 (1 << _ALLOC_dirid_groups) | (1 << _ALLOC_packing_groups)))
697 return;
698
699 seq_puts(seq, ",alloc=");
700
701 if (TEST_OPTION(concentrating_formatted_nodes, s)) {
702 print_sep(seq, &first);
703 if (REISERFS_SB(s)->s_alloc_options.border != 10) {
704 seq_printf(seq, "concentrating_formatted_nodes=%d",
705 100 / REISERFS_SB(s)->s_alloc_options.border);
706 } else
707 seq_puts(seq, "concentrating_formatted_nodes");
708 }
709 if (TEST_OPTION(displacing_large_files, s)) {
710 print_sep(seq, &first);
711 if (REISERFS_SB(s)->s_alloc_options.large_file_size != 16) {
712 seq_printf(seq, "displacing_large_files=%lu",
713 REISERFS_SB(s)->s_alloc_options.large_file_size);
714 } else
715 seq_puts(seq, "displacing_large_files");
716 }
717 if (TEST_OPTION(displacing_new_packing_localities, s)) {
718 print_sep(seq, &first);
719 seq_puts(seq, "displacing_new_packing_localities");
720 }
721 if (TEST_OPTION(old_hashed_relocation, s)) {
722 print_sep(seq, &first);
723 seq_puts(seq, "old_hashed_relocation");
724 }
725 if (TEST_OPTION(new_hashed_relocation, s)) {
726 print_sep(seq, &first);
727 seq_puts(seq, "new_hashed_relocation");
728 }
729 if (TEST_OPTION(dirid_groups, s)) {
730 print_sep(seq, &first);
731 seq_puts(seq, "dirid_groups");
732 }
733 if (TEST_OPTION(oid_groups, s)) {
734 print_sep(seq, &first);
735 seq_puts(seq, "oid_groups");
736 }
737 if (TEST_OPTION(packing_groups, s)) {
738 print_sep(seq, &first);
739 seq_puts(seq, "packing_groups");
740 }
741 if (TEST_OPTION(hashed_formatted_nodes, s)) {
742 print_sep(seq, &first);
743 seq_puts(seq, "hashed_formatted_nodes");
744 }
745 if (TEST_OPTION(skip_busy, s)) {
746 print_sep(seq, &first);
747 seq_puts(seq, "skip_busy");
748 }
749 if (TEST_OPTION(hundredth_slices, s)) {
750 print_sep(seq, &first);
751 seq_puts(seq, "hundredth_slices");
752 }
753 if (TEST_OPTION(old_way, s)) {
754 print_sep(seq, &first);
755 seq_puts(seq, "old_way");
756 }
757 if (TEST_OPTION(displace_based_on_dirid, s)) {
758 print_sep(seq, &first);
759 seq_puts(seq, "displace_based_on_dirid");
760 }
761 if (REISERFS_SB(s)->s_alloc_options.preallocmin != 0) {
762 print_sep(seq, &first);
763 seq_printf(seq, "preallocmin=%d",
764 REISERFS_SB(s)->s_alloc_options.preallocmin);
765 }
766 if (REISERFS_SB(s)->s_alloc_options.preallocsize != 17) {
767 print_sep(seq, &first);
768 seq_printf(seq, "preallocsize=%d",
769 REISERFS_SB(s)->s_alloc_options.preallocsize);
770 }
771}
772
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700773static inline void new_hashed_relocation(reiserfs_blocknr_hint_t * hint)
774{
775 char *hash_in;
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700776
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700777 if (hint->formatted_node) {
778 hash_in = (char *)&hint->key.k_dir_id;
779 } else {
780 if (!hint->inode) {
Jeff Mahoney098297b2014-04-23 10:00:36 -0400781 /*hint->search_start = hint->beg;*/
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700782 hash_in = (char *)&hint->key.k_dir_id;
783 } else
784 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
785 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
786 else
787 hash_in =
788 (char *)(&INODE_PKEY(hint->inode)->k_objectid);
789 }
790
791 hint->search_start =
792 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700793}
794
795/*
796 * Relocation based on dirid, hashing them into a given bitmap block
Joe Perchesc78bad12008-02-03 17:33:42 +0200797 * files. Formatted nodes are unaffected, a separate policy covers them
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700799static void dirid_groups(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700800{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700801 unsigned long hash;
802 __u32 dirid = 0;
803 int bm = 0;
804 struct super_block *sb = hint->th->t_super;
Fabian Frederickae0a50a2014-06-06 14:38:11 -0700805
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 if (hint->inode)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700807 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
808 else if (hint->formatted_node)
809 dirid = hint->key.k_dir_id;
810
811 if (dirid) {
812 bm = bmap_hash_id(sb, dirid);
813 hash = bm * (sb->s_blocksize << 3);
814 /* give a portion of the block group to metadata */
815 if (hint->inode)
816 hash += sb->s_blocksize / 2;
817 hint->search_start = hash;
818 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819}
820
821/*
822 * Relocation based on oid, hashing them into a given bitmap block
Joe Perchesc78bad12008-02-03 17:33:42 +0200823 * files. Formatted nodes are unaffected, a separate policy covers them
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700825static void oid_groups(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700827 if (hint->inode) {
828 unsigned long hash;
829 __u32 oid;
830 __u32 dirid;
831 int bm;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700833 dirid = le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700834
Jeff Mahoney098297b2014-04-23 10:00:36 -0400835 /*
836 * keep the root dir and it's first set of subdirs close to
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700837 * the start of the disk
838 */
839 if (dirid <= 2)
840 hash = (hint->inode->i_sb->s_blocksize << 3);
841 else {
842 oid = le32_to_cpu(INODE_PKEY(hint->inode)->k_objectid);
843 bm = bmap_hash_id(hint->inode->i_sb, oid);
844 hash = bm * (hint->inode->i_sb->s_blocksize << 3);
845 }
846 hint->search_start = hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848}
849
Jeff Mahoney098297b2014-04-23 10:00:36 -0400850/*
851 * returns 1 if it finds an indirect item and gets valid hint info
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852 * from it, otherwise 0
853 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700854static int get_left_neighbor(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700855{
Josef "Jeff" Sipekfec6d052006-12-08 02:36:32 -0800856 struct treepath *path;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700857 struct buffer_head *bh;
858 struct item_head *ih;
859 int pos_in_item;
860 __le32 *item;
861 int ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862
Jeff Mahoney098297b2014-04-23 10:00:36 -0400863 /*
864 * reiserfs code can call this function w/o pointer to path
865 * structure supplied; then we rely on supplied search_start
866 */
867 if (!hint->path)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700868 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700870 path = hint->path;
871 bh = get_last_bh(path);
872 RFALSE(!bh, "green-4002: Illegal path specified to get_left_neighbor");
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400873 ih = tp_item_head(path);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700874 pos_in_item = path->pos_in_item;
Jeff Mahoney4cf5f7a2014-04-23 10:00:35 -0400875 item = tp_item_body(path);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700877 hint->search_start = bh->b_blocknr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878
Jeff Mahoney098297b2014-04-23 10:00:36 -0400879 /*
880 * for indirect item: go to left and look for the first non-hole entry
881 * in the indirect item
882 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700883 if (!hint->formatted_node && is_indirect_le_ih(ih)) {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700884 if (pos_in_item == I_UNFM_NUM(ih))
885 pos_in_item--;
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700886 while (pos_in_item >= 0) {
887 int t = get_block_num(item, pos_in_item);
888 if (t) {
889 hint->search_start = t;
890 ret = 1;
891 break;
892 }
893 pos_in_item--;
894 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700897 /* does result value fit into specified region? */
898 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899}
900
Jeff Mahoney098297b2014-04-23 10:00:36 -0400901/*
902 * should be, if formatted node, then try to put on first part of the device
903 * specified as number of percent with mount option device, else try to put
904 * on last of device. This is not to say it is good code to do so,
905 * but the effect should be measured.
906 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700907static inline void set_border_in_hint(struct super_block *s,
908 reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700909{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700910 b_blocknr_t border =
911 SB_BLOCK_COUNT(s) / REISERFS_SB(s)->s_alloc_options.border;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700913 if (hint->formatted_node)
914 hint->end = border - 1;
915 else
916 hint->beg = border;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700917}
918
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700919static inline void displace_large_file(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700920{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700921 if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
922 hint->search_start =
923 hint->beg +
924 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_dir_id),
925 4) % (hint->end - hint->beg);
926 else
927 hint->search_start =
928 hint->beg +
929 keyed_hash((char *)(&INODE_PKEY(hint->inode)->k_objectid),
930 4) % (hint->end - hint->beg);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931}
932
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700933static inline void hash_formatted_node(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700935 char *hash_in;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700937 if (!hint->inode)
938 hash_in = (char *)&hint->key.k_dir_id;
939 else if (TEST_OPTION(displace_based_on_dirid, hint->th->t_super))
940 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_dir_id);
941 else
942 hash_in = (char *)(&INODE_PKEY(hint->inode)->k_objectid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700943
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700944 hint->search_start =
945 hint->beg + keyed_hash(hash_in, 4) % (hint->end - hint->beg);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700946}
947
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700948static inline int
949this_blocknr_allocation_would_make_it_a_large_file(reiserfs_blocknr_hint_t *
950 hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700951{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700952 return hint->block ==
953 REISERFS_SB(hint->th->t_super)->s_alloc_options.large_file_size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954}
955
956#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700957static inline void displace_new_packing_locality(reiserfs_blocknr_hint_t * hint)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700959 struct in_core_key *key = &hint->key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700960
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700961 hint->th->displace_new_blocks = 0;
962 hint->search_start =
963 hint->beg + keyed_hash((char *)(&key->k_objectid),
964 4) % (hint->end - hint->beg);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700965}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700968static inline int old_hashed_relocation(reiserfs_blocknr_hint_t * hint)
969{
970 b_blocknr_t border;
971 u32 hash_in;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700972
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700973 if (hint->formatted_node || hint->inode == NULL) {
974 return 0;
975 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700976
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700977 hash_in = le32_to_cpu((INODE_PKEY(hint->inode))->k_dir_id);
978 border =
979 hint->beg + (u32) keyed_hash(((char *)(&hash_in)),
980 4) % (hint->end - hint->beg - 1);
981 if (border > hint->search_start)
982 hint->search_start = border;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983
Linus Torvaldsbd4c6252005-07-12 20:21:28 -0700984 return 1;
985}
986
987static inline int old_way(reiserfs_blocknr_hint_t * hint)
988{
989 b_blocknr_t border;
990
991 if (hint->formatted_node || hint->inode == NULL) {
992 return 0;
993 }
994
995 border =
996 hint->beg +
997 le32_to_cpu(INODE_PKEY(hint->inode)->k_dir_id) % (hint->end -
998 hint->beg);
999 if (border > hint->search_start)
1000 hint->search_start = border;
1001
1002 return 1;
1003}
1004
1005static inline void hundredth_slices(reiserfs_blocknr_hint_t * hint)
1006{
1007 struct in_core_key *key = &hint->key;
1008 b_blocknr_t slice_start;
1009
1010 slice_start =
1011 (keyed_hash((char *)(&key->k_dir_id), 4) % 100) * (hint->end / 100);
1012 if (slice_start > hint->search_start
1013 || slice_start + (hint->end / 100) <= hint->search_start) {
1014 hint->search_start = slice_start;
1015 }
1016}
1017
1018static void determine_search_start(reiserfs_blocknr_hint_t * hint,
1019 int amount_needed)
1020{
1021 struct super_block *s = hint->th->t_super;
1022 int unfm_hint;
1023
1024 hint->beg = 0;
1025 hint->end = SB_BLOCK_COUNT(s) - 1;
1026
1027 /* This is former border algorithm. Now with tunable border offset */
1028 if (concentrating_formatted_nodes(s))
1029 set_border_in_hint(s, hint);
1030
1031#ifdef DISPLACE_NEW_PACKING_LOCALITIES
Jeff Mahoney098297b2014-04-23 10:00:36 -04001032 /*
1033 * whenever we create a new directory, we displace it. At first
1034 * we will hash for location, later we might look for a moderately
1035 * empty place for it
1036 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001037 if (displacing_new_packing_localities(s)
1038 && hint->th->displace_new_blocks) {
1039 displace_new_packing_locality(hint);
1040
Jeff Mahoney098297b2014-04-23 10:00:36 -04001041 /*
1042 * we do not continue determine_search_start,
1043 * if new packing locality is being displaced
1044 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001045 return;
1046 }
1047#endif
1048
Jeff Mahoney098297b2014-04-23 10:00:36 -04001049 /*
1050 * all persons should feel encouraged to add more special cases
1051 * here and test them
1052 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001053
1054 if (displacing_large_files(s) && !hint->formatted_node
1055 && this_blocknr_allocation_would_make_it_a_large_file(hint)) {
1056 displace_large_file(hint);
1057 return;
1058 }
1059
Jeff Mahoney098297b2014-04-23 10:00:36 -04001060 /*
1061 * if none of our special cases is relevant, use the left
1062 * neighbor in the tree order of the new node we are allocating for
1063 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001064 if (hint->formatted_node && TEST_OPTION(hashed_formatted_nodes, s)) {
1065 hash_formatted_node(hint);
1066 return;
1067 }
1068
1069 unfm_hint = get_left_neighbor(hint);
1070
Jeff Mahoney098297b2014-04-23 10:00:36 -04001071 /*
1072 * Mimic old block allocator behaviour, that is if VFS allowed for
1073 * preallocation, new blocks are displaced based on directory ID.
1074 * Also, if suggested search_start is less than last preallocated
1075 * block, we start searching from it, assuming that HDD dataflow
1076 * is faster in forward direction
1077 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001078 if (TEST_OPTION(old_way, s)) {
1079 if (!hint->formatted_node) {
1080 if (!reiserfs_hashed_relocation(s))
1081 old_way(hint);
1082 else if (!reiserfs_no_unhashed_relocation(s))
1083 old_hashed_relocation(hint);
1084
1085 if (hint->inode
1086 && hint->search_start <
1087 REISERFS_I(hint->inode)->i_prealloc_block)
1088 hint->search_start =
1089 REISERFS_I(hint->inode)->i_prealloc_block;
1090 }
1091 return;
1092 }
1093
1094 /* This is an approach proposed by Hans */
1095 if (TEST_OPTION(hundredth_slices, s)
1096 && !(displacing_large_files(s) && !hint->formatted_node)) {
1097 hundredth_slices(hint);
1098 return;
1099 }
1100
1101 /* old_hashed_relocation only works on unformatted */
1102 if (!unfm_hint && !hint->formatted_node &&
1103 TEST_OPTION(old_hashed_relocation, s)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001104 old_hashed_relocation(hint);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001105 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001106
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001107 /* new_hashed_relocation works with both formatted/unformatted nodes */
1108 if ((!unfm_hint || hint->formatted_node) &&
1109 TEST_OPTION(new_hashed_relocation, s)) {
1110 new_hashed_relocation(hint);
1111 }
Jeff Mahoney098297b2014-04-23 10:00:36 -04001112
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001113 /* dirid grouping works only on unformatted nodes */
1114 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
1115 dirid_groups(hint);
1116 }
1117#ifdef DISPLACE_NEW_PACKING_LOCALITIES
1118 if (hint->formatted_node && TEST_OPTION(dirid_groups, s)) {
1119 dirid_groups(hint);
1120 }
1121#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001123 /* oid grouping works only on unformatted nodes */
1124 if (!unfm_hint && !hint->formatted_node && TEST_OPTION(oid_groups, s)) {
1125 oid_groups(hint);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001126 }
1127 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001128}
1129
1130static int determine_prealloc_size(reiserfs_blocknr_hint_t * hint)
1131{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001132 /* make minimum size a mount option and benchmark both ways */
1133 /* we preallocate blocks only for regular files, specific size */
1134 /* benchmark preallocating always and see what happens */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001136 hint->prealloc_size = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001138 if (!hint->formatted_node && hint->preallocate) {
Jeff Mahoney54930df2017-06-22 16:35:04 -04001139 if (S_ISREG(hint->inode->i_mode) && !IS_PRIVATE(hint->inode)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001140 && hint->inode->i_size >=
1141 REISERFS_SB(hint->th->t_super)->s_alloc_options.
1142 preallocmin * hint->inode->i_sb->s_blocksize)
1143 hint->prealloc_size =
1144 REISERFS_SB(hint->th->t_super)->s_alloc_options.
1145 preallocsize - 1;
1146 }
1147 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148}
1149
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001150static inline int allocate_without_wrapping_disk(reiserfs_blocknr_hint_t * hint,
1151 b_blocknr_t * new_blocknrs,
1152 b_blocknr_t start,
1153 b_blocknr_t finish, int min,
1154 int amount_needed,
1155 int prealloc_size)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001156{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001157 int rest = amount_needed;
1158 int nr_allocated;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001160 while (rest > 0 && start <= finish) {
1161 nr_allocated = scan_bitmap(hint->th, &start, finish, min,
1162 rest + prealloc_size,
1163 !hint->formatted_node, hint->block);
1164
1165 if (nr_allocated == 0) /* no new blocks allocated, return */
1166 break;
1167
1168 /* fill free_blocknrs array first */
1169 while (rest > 0 && nr_allocated > 0) {
1170 *new_blocknrs++ = start++;
1171 rest--;
1172 nr_allocated--;
1173 }
1174
1175 /* do we have something to fill prealloc. array also ? */
1176 if (nr_allocated > 0) {
Jeff Mahoney098297b2014-04-23 10:00:36 -04001177 /*
1178 * it means prealloc_size was greater that 0 and
1179 * we do preallocation
1180 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001181 list_add(&REISERFS_I(hint->inode)->i_prealloc_list,
1182 &SB_JOURNAL(hint->th->t_super)->
1183 j_prealloc_list);
1184 REISERFS_I(hint->inode)->i_prealloc_block = start;
1185 REISERFS_I(hint->inode)->i_prealloc_count =
1186 nr_allocated;
1187 break;
1188 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001189 }
1190
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001191 return (amount_needed - rest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192}
1193
1194static inline int blocknrs_and_prealloc_arrays_from_search_start
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001195 (reiserfs_blocknr_hint_t * hint, b_blocknr_t * new_blocknrs,
1196 int amount_needed) {
1197 struct super_block *s = hint->th->t_super;
1198 b_blocknr_t start = hint->search_start;
1199 b_blocknr_t finish = SB_BLOCK_COUNT(s) - 1;
1200 int passno = 0;
1201 int nr_allocated = 0;
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001202 int depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001203
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001204 determine_prealloc_size(hint);
1205 if (!hint->formatted_node) {
1206 int quota_ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001207#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001208 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1209 "reiserquota: allocating %d blocks id=%u",
1210 amount_needed, hint->inode->i_uid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001212 depth = reiserfs_write_unlock_nested(s);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001213 quota_ret =
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001214 dquot_alloc_block_nodirty(hint->inode, amount_needed);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001215 if (quota_ret) { /* Quota exceeded? */
1216 reiserfs_write_lock_nested(s, depth);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001217 return QUOTA_EXCEEDED;
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001218 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001219 if (hint->preallocate && hint->prealloc_size) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001220#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001221 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1222 "reiserquota: allocating (prealloc) %d blocks id=%u",
1223 hint->prealloc_size, hint->inode->i_uid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224#endif
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001225 quota_ret = dquot_prealloc_block_nodirty(hint->inode,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001226 hint->prealloc_size);
1227 if (quota_ret)
1228 hint->preallocate = hint->prealloc_size = 0;
1229 }
1230 /* for unformatted nodes, force large allocations */
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001231 reiserfs_write_lock_nested(s, depth);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001232 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001233
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001234 do {
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001235 switch (passno++) {
1236 case 0: /* Search from hint->search_start to end of disk */
1237 start = hint->search_start;
1238 finish = SB_BLOCK_COUNT(s) - 1;
1239 break;
1240 case 1: /* Search from hint->beg to hint->search_start */
1241 start = hint->beg;
1242 finish = hint->search_start;
1243 break;
1244 case 2: /* Last chance: Search from 0 to hint->beg */
1245 start = 0;
1246 finish = hint->beg;
1247 break;
Jeff Mahoney098297b2014-04-23 10:00:36 -04001248 default:
1249 /* We've tried searching everywhere, not enough space */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001250 /* Free the blocks */
1251 if (!hint->formatted_node) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001253 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1254 "reiserquota: freeing (nospace) %d blocks id=%u",
1255 amount_needed +
1256 hint->prealloc_size -
1257 nr_allocated,
1258 hint->inode->i_uid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001259#endif
Jan Kara77db4f22009-01-26 17:14:18 +01001260 /* Free not allocated blocks */
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001261 depth = reiserfs_write_unlock_nested(s);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001262 dquot_free_block_nodirty(hint->inode,
Jan Kara77db4f22009-01-26 17:14:18 +01001263 amount_needed + hint->prealloc_size -
1264 nr_allocated);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001265 reiserfs_write_lock_nested(s, depth);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001266 }
1267 while (nr_allocated--)
1268 reiserfs_free_block(hint->th, hint->inode,
1269 new_blocknrs[nr_allocated],
1270 !hint->formatted_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001272 return NO_DISK_SPACE;
1273 }
1274 } while ((nr_allocated += allocate_without_wrapping_disk(hint,
1275 new_blocknrs +
1276 nr_allocated,
1277 start, finish,
Jeff Mahoney9ea0f942006-09-30 23:28:45 -07001278 1,
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001279 amount_needed -
1280 nr_allocated,
1281 hint->
1282 prealloc_size))
1283 < amount_needed);
1284 if (!hint->formatted_node &&
1285 amount_needed + hint->prealloc_size >
1286 nr_allocated + REISERFS_I(hint->inode)->i_prealloc_count) {
1287 /* Some of preallocation blocks were not allocated */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001288#ifdef REISERQUOTA_DEBUG
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001289 reiserfs_debug(s, REISERFS_DEBUG_CODE,
1290 "reiserquota: freeing (failed prealloc) %d blocks id=%u",
1291 amount_needed + hint->prealloc_size -
1292 nr_allocated -
1293 REISERFS_I(hint->inode)->i_prealloc_count,
1294 hint->inode->i_uid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295#endif
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001296
1297 depth = reiserfs_write_unlock_nested(s);
Christoph Hellwig5dd40562010-03-03 09:05:00 -05001298 dquot_free_block_nodirty(hint->inode, amount_needed +
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001299 hint->prealloc_size - nr_allocated -
1300 REISERFS_I(hint->inode)->
1301 i_prealloc_count);
Jeff Mahoneyd2d03952013-08-08 17:34:47 -04001302 reiserfs_write_lock_nested(s, depth);
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001303 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001305 return CARRY_ON;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306}
1307
1308/* grab new blocknrs from preallocated list */
1309/* return amount still needed after using them */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001310static int use_preallocated_list_if_available(reiserfs_blocknr_hint_t * hint,
1311 b_blocknr_t * new_blocknrs,
1312 int amount_needed)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001314 struct inode *inode = hint->inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001316 if (REISERFS_I(inode)->i_prealloc_count > 0) {
1317 while (amount_needed) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001318
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001319 *new_blocknrs++ = REISERFS_I(inode)->i_prealloc_block++;
1320 REISERFS_I(inode)->i_prealloc_count--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001321
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001322 amount_needed--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001323
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001324 if (REISERFS_I(inode)->i_prealloc_count <= 0) {
1325 list_del(&REISERFS_I(inode)->i_prealloc_list);
1326 break;
1327 }
1328 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001330 /* return amount still needed after using preallocated blocks */
1331 return amount_needed;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332}
1333
Jeff Mahoney098297b2014-04-23 10:00:36 -04001334int reiserfs_allocate_blocknrs(reiserfs_blocknr_hint_t *hint,
1335 b_blocknr_t *new_blocknrs,
1336 int amount_needed,
1337 /* Amount of blocks we have already reserved */
1338 int reserved_by_us)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001339{
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001340 int initial_amount_needed = amount_needed;
1341 int ret;
1342 struct super_block *s = hint->th->t_super;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001343
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001344 /* Check if there is enough space, taking into account reserved space */
1345 if (SB_FREE_BLOCKS(s) - REISERFS_SB(s)->reserved_blocks <
1346 amount_needed - reserved_by_us)
1347 return NO_DISK_SPACE;
1348 /* should this be if !hint->inode && hint->preallocate? */
1349 /* do you mean hint->formatted_node can be removed ? - Zam */
Jeff Mahoney098297b2014-04-23 10:00:36 -04001350 /*
1351 * hint->formatted_node cannot be removed because we try to access
1352 * inode information here, and there is often no inode associated with
1353 * metadata allocations - green
1354 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001355
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001356 if (!hint->formatted_node && hint->preallocate) {
1357 amount_needed = use_preallocated_list_if_available
1358 (hint, new_blocknrs, amount_needed);
Jeff Mahoney098297b2014-04-23 10:00:36 -04001359
1360 /*
1361 * We have all the block numbers we need from the
1362 * prealloc list
1363 */
1364 if (amount_needed == 0)
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001365 return CARRY_ON;
1366 new_blocknrs += (initial_amount_needed - amount_needed);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001367 }
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001368
1369 /* find search start and save it in hint structure */
1370 determine_search_start(hint, amount_needed);
1371 if (hint->search_start >= SB_BLOCK_COUNT(s))
1372 hint->search_start = SB_BLOCK_COUNT(s) - 1;
1373
1374 /* allocation itself; fill new_blocknrs and preallocation arrays */
1375 ret = blocknrs_and_prealloc_arrays_from_search_start
1376 (hint, new_blocknrs, amount_needed);
1377
Jeff Mahoney098297b2014-04-23 10:00:36 -04001378 /*
1379 * We used prealloc. list to fill (partially) new_blocknrs array.
1380 * If final allocation fails we need to return blocks back to
1381 * prealloc. list or just free them. -- Zam (I chose second
1382 * variant)
1383 */
Linus Torvaldsbd4c6252005-07-12 20:21:28 -07001384 if (ret != CARRY_ON) {
1385 while (amount_needed++ < initial_amount_needed) {
1386 reiserfs_free_block(hint->th, hint->inode,
1387 *(--new_blocknrs), 1);
1388 }
1389 }
1390 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391}
1392
Jeff Mahoney6f010462006-09-30 23:28:43 -07001393void reiserfs_cache_bitmap_metadata(struct super_block *sb,
1394 struct buffer_head *bh,
1395 struct reiserfs_bitmap_info *info)
1396{
1397 unsigned long *cur = (unsigned long *)(bh->b_data + bh->b_size);
1398
Jeff Mahoney4d208512007-10-18 23:39:26 -07001399 /* The first bit must ALWAYS be 1 */
Jeff Mahoney0030b642009-03-30 14:02:28 -04001400 if (!reiserfs_test_le_bit(0, (unsigned long *)bh->b_data))
1401 reiserfs_error(sb, "reiserfs-2025", "bitmap block %lu is "
1402 "corrupted: first bit must be 1", bh->b_blocknr);
Jeff Mahoney4d208512007-10-18 23:39:26 -07001403
1404 info->free_count = 0;
Jeff Mahoney6f010462006-09-30 23:28:43 -07001405
1406 while (--cur >= (unsigned long *)bh->b_data) {
Jeff Mahoney6f010462006-09-30 23:28:43 -07001407 /* 0 and ~0 are special, we can optimize for them */
Jeff Mahoney4d208512007-10-18 23:39:26 -07001408 if (*cur == 0)
Jeff Mahoney6f010462006-09-30 23:28:43 -07001409 info->free_count += BITS_PER_LONG;
Jeff Mahoney4d208512007-10-18 23:39:26 -07001410 else if (*cur != ~0L) /* A mix, investigate */
Akinobu Mita9d6bf5a2011-07-25 17:13:38 -07001411 info->free_count += BITS_PER_LONG - hweight_long(*cur);
Jeff Mahoney6f010462006-09-30 23:28:43 -07001412 }
Jeff Mahoney6f010462006-09-30 23:28:43 -07001413}
1414
1415struct buffer_head *reiserfs_read_bitmap_block(struct super_block *sb,
1416 unsigned int bitmap)
1417{
1418 b_blocknr_t block = (sb->s_blocksize << 3) * bitmap;
Jeff Mahoney50652272006-09-30 23:28:44 -07001419 struct reiserfs_bitmap_info *info = SB_AP_BITMAP(sb) + bitmap;
Jeff Mahoney6f010462006-09-30 23:28:43 -07001420 struct buffer_head *bh;
1421
Jeff Mahoney098297b2014-04-23 10:00:36 -04001422 /*
1423 * Way old format filesystems had the bitmaps packed up front.
1424 * I doubt there are any of these left, but just in case...
1425 */
Jeff Mahoney6f010462006-09-30 23:28:43 -07001426 if (unlikely(test_bit(REISERFS_OLD_FORMAT,
Jeff Mahoneya228bf82014-04-23 10:00:42 -04001427 &REISERFS_SB(sb)->s_properties)))
Jeff Mahoney6f010462006-09-30 23:28:43 -07001428 block = REISERFS_SB(sb)->s_sbh->b_blocknr + 1 + bitmap;
1429 else if (bitmap == 0)
1430 block = (REISERFS_DISK_OFFSET_IN_BYTES >> sb->s_blocksize_bits) + 1;
1431
Jeff Mahoney50652272006-09-30 23:28:44 -07001432 bh = sb_bread(sb, block);
1433 if (bh == NULL)
Eric Eric Sesterhenn00079e02006-10-06 22:19:45 -07001434 reiserfs_warning(sb, "sh-2029: %s: bitmap block (#%u) "
Harvey Harrisonfbe54982008-04-28 02:16:22 -07001435 "reading failed", __func__, block);
Jeff Mahoney50652272006-09-30 23:28:44 -07001436 else {
1437 if (buffer_locked(bh)) {
Jeff Mahoney278f6672013-08-08 17:34:46 -04001438 int depth;
Jeff Mahoney50652272006-09-30 23:28:44 -07001439 PROC_INFO_INC(sb, scan_bitmap.wait);
Jeff Mahoney278f6672013-08-08 17:34:46 -04001440 depth = reiserfs_write_unlock_nested(sb);
Jeff Mahoney50652272006-09-30 23:28:44 -07001441 __wait_on_buffer(bh);
Jeff Mahoney278f6672013-08-08 17:34:46 -04001442 reiserfs_write_lock_nested(sb, depth);
Jeff Mahoney50652272006-09-30 23:28:44 -07001443 }
1444 BUG_ON(!buffer_uptodate(bh));
1445 BUG_ON(atomic_read(&bh->b_count) == 0);
1446
Jeff Mahoney4d208512007-10-18 23:39:26 -07001447 if (info->free_count == UINT_MAX)
Jeff Mahoney50652272006-09-30 23:28:44 -07001448 reiserfs_cache_bitmap_metadata(sb, bh, info);
1449 }
Jeff Mahoney6f010462006-09-30 23:28:43 -07001450
1451 return bh;
1452}
1453
1454int reiserfs_init_bitmap_cache(struct super_block *sb)
1455{
1456 struct reiserfs_bitmap_info *bitmap;
Jeff Mahoneycb680c12007-10-18 23:39:27 -07001457 unsigned int bmap_nr = reiserfs_bmap_count(sb);
Jeff Mahoney6f010462006-09-30 23:28:43 -07001458
Kees Cook42bc47b2018-06-12 14:27:11 -07001459 bitmap = vmalloc(array_size(bmap_nr, sizeof(*bitmap)));
Jeff Mahoney6f010462006-09-30 23:28:43 -07001460 if (bitmap == NULL)
1461 return -ENOMEM;
1462
Jeff Mahoneycb680c12007-10-18 23:39:27 -07001463 memset(bitmap, 0xff, sizeof(*bitmap) * bmap_nr);
Jeff Mahoney6f010462006-09-30 23:28:43 -07001464
Jeff Mahoney6f010462006-09-30 23:28:43 -07001465 SB_AP_BITMAP(sb) = bitmap;
1466
1467 return 0;
1468}
Jeff Mahoney50652272006-09-30 23:28:44 -07001469
1470void reiserfs_free_bitmap_cache(struct super_block *sb)
1471{
1472 if (SB_AP_BITMAP(sb)) {
1473 vfree(SB_AP_BITMAP(sb));
1474 SB_AP_BITMAP(sb) = NULL;
1475 }
1476}