blob: 42694e11c23de46b25f1177888b97ec2aac1cf32 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * linux/fs/ufs/balloc.c
3 *
4 * Copyright (C) 1998
5 * Daniel Pirkl <daniel.pirkl@email.cz>
6 * Charles University, Faculty of Mathematics and Physics
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -08007 *
8 * UFS2 write support Evgeniy Dushistov <dushistov@mail.ru>, 2007
Linus Torvalds1da177e2005-04-16 15:20:36 -07009 */
10
11#include <linux/fs.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070012#include <linux/stat.h>
13#include <linux/time.h>
14#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015#include <linux/buffer_head.h>
Randy Dunlap16f7e0f2006-01-11 12:17:46 -080016#include <linux/capability.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/bitops.h>
18#include <asm/byteorder.h>
19
Mike Frysingere5420592008-02-08 04:21:31 -080020#include "ufs_fs.h"
Christoph Hellwigbcd6d4e2007-10-16 23:26:51 -070021#include "ufs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#include "swab.h"
23#include "util.h"
24
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080025#define INVBLOCK ((u64)-1L)
26
27static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned, int *);
28static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);
29static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);
30static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);
Linus Torvalds1da177e2005-04-16 15:20:36 -070031static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
32static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
33
34/*
35 * Free 'count' fragments from fragment number 'fragment'
36 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080037void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -070038{
Linus Torvalds1da177e2005-04-16 15:20:36 -070039 struct super_block * sb;
40 struct ufs_sb_private_info * uspi;
41 struct ufs_super_block_first * usb1;
42 struct ufs_cg_private_info * ucpi;
43 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080044 unsigned cgno, bit, end_bit, bbase, blkmap, i;
45 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -070046
47 sb = inode->i_sb;
48 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +030049 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -070050
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080051 UFSD("ENTER, fragment %llu, count %u\n",
52 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -070053
54 if (ufs_fragnum(fragment) + count > uspi->s_fpg)
55 ufs_error (sb, "ufs_free_fragments", "internal error");
56
57 lock_super(sb);
58
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080059 cgno = ufs_dtog(uspi, fragment);
60 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -070061 if (cgno >= uspi->s_ncg) {
62 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
63 goto failed;
64 }
65
66 ucpi = ufs_load_cylinder (sb, cgno);
67 if (!ucpi)
68 goto failed;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070069 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -070070 if (!ufs_cg_chkmagic(sb, ucg)) {
71 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
72 goto failed;
73 }
74
75 end_bit = bit + count;
76 bbase = ufs_blknum (bit);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070077 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070078 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
79 for (i = bit; i < end_bit; i++) {
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070080 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, i))
81 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);
Evgeniy7b4ee732006-01-14 11:42:06 +030082 else
83 ufs_error (sb, "ufs_free_fragments",
84 "bit already cleared for fragment %u", i);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 }
86
Linus Torvalds1da177e2005-04-16 15:20:36 -070087 fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -070088 uspi->cs_total.cs_nffree += count;
Linus Torvalds1da177e2005-04-16 15:20:36 -070089 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070090 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070091 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
92
93 /*
94 * Trying to reassemble free fragments into block
95 */
96 blkno = ufs_fragstoblks (bbase);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070097 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -070099 uspi->cs_total.cs_nffree -= uspi->s_fpb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
101 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
102 ufs_clusteracct (sb, ucpi, blkno, 1);
103 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700104 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700105 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800106 if (uspi->fs_magic != UFS2_MAGIC) {
107 unsigned cylno = ufs_cbtocylno (bbase);
108
109 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
110 ufs_cbtorpos(bbase)), 1);
111 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
112 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113 }
114
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700115 ubh_mark_buffer_dirty (USPI_UBH(uspi));
116 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200117 if (sb->s_flags & MS_SYNCHRONOUS)
118 ubh_sync_block(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119 sb->s_dirt = 1;
120
121 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700122 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700123 return;
124
125failed:
126 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700127 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128 return;
129}
130
131/*
132 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
133 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800134void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700135{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 struct super_block * sb;
137 struct ufs_sb_private_info * uspi;
138 struct ufs_super_block_first * usb1;
139 struct ufs_cg_private_info * ucpi;
140 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800141 unsigned overflow, cgno, bit, end_bit, i;
142 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143
144 sb = inode->i_sb;
145 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300146 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800148 UFSD("ENTER, fragment %llu, count %u\n",
149 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150
151 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
152 ufs_error (sb, "ufs_free_blocks", "internal error, "
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800153 "fragment %llu, count %u\n",
154 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155 goto failed;
156 }
157
158 lock_super(sb);
159
160do_more:
161 overflow = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800162 cgno = ufs_dtog(uspi, fragment);
163 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 if (cgno >= uspi->s_ncg) {
165 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700166 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167 }
168 end_bit = bit + count;
169 if (end_bit > uspi->s_fpg) {
170 overflow = bit + count - uspi->s_fpg;
171 count -= overflow;
172 end_bit -= overflow;
173 }
174
175 ucpi = ufs_load_cylinder (sb, cgno);
176 if (!ucpi)
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700177 goto failed_unlock;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700178 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700179 if (!ufs_cg_chkmagic(sb, ucg)) {
180 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700181 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700182 }
183
184 for (i = bit; i < end_bit; i += uspi->s_fpb) {
185 blkno = ufs_fragstoblks(i);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700186 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700187 ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
188 }
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700189 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
191 ufs_clusteracct (sb, ucpi, blkno, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192
193 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700194 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800196
197 if (uspi->fs_magic != UFS2_MAGIC) {
198 unsigned cylno = ufs_cbtocylno(i);
199
200 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
201 ufs_cbtorpos(i)), 1);
202 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
203 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204 }
205
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700206 ubh_mark_buffer_dirty (USPI_UBH(uspi));
207 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200208 if (sb->s_flags & MS_SYNCHRONOUS)
209 ubh_sync_block(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210
211 if (overflow) {
212 fragment += count;
213 count = overflow;
214 goto do_more;
215 }
216
217 sb->s_dirt = 1;
218 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700219 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220 return;
221
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700222failed_unlock:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223 unlock_super (sb);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700224failed:
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700225 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226 return;
227}
228
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700229/*
230 * Modify inode page cache in such way:
231 * have - blocks with b_blocknr equal to oldb...oldb+count-1
232 * get - blocks with b_blocknr equal to newb...newb+count-1
233 * also we suppose that oldb...oldb+count-1 blocks
234 * situated at the end of file.
235 *
236 * We can come here from ufs_writepage or ufs_prepare_write,
237 * locked_page is argument of these functions, so we already lock it.
238 */
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800239static void ufs_change_blocknr(struct inode *inode, sector_t beg,
240 unsigned int count, sector_t oldb,
241 sector_t newb, struct page *locked_page)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700242{
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800243 const unsigned blks_per_page =
244 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
245 const unsigned mask = blks_per_page - 1;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800246 struct address_space * const mapping = inode->i_mapping;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800247 pgoff_t index, cur_index, last_index;
248 unsigned pos, j, lblock;
249 sector_t end, i;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700250 struct page *page;
251 struct buffer_head *head, *bh;
252
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800253 UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",
254 inode->i_ino, count,
255 (unsigned long long)oldb, (unsigned long long)newb);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700256
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800257 BUG_ON(!locked_page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700258 BUG_ON(!PageLocked(locked_page));
259
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800260 cur_index = locked_page->index;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800261 end = count + beg;
262 last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
263 for (i = beg; i < end; i = (i | mask) + 1) {
264 index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700265
266 if (likely(cur_index != index)) {
267 page = ufs_get_locked_page(mapping, index);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800268 if (!page)/* it was truncated */
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700269 continue;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800270 if (IS_ERR(page)) {/* or EIO */
Harvey Harrison97460772008-04-28 02:16:17 -0700271 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800272 "read of page %llu failed\n",
273 (unsigned long long)index);
274 continue;
275 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700276 } else
277 page = locked_page;
278
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700279 head = page_buffers(page);
280 bh = head;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800281 pos = i & mask;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800282 for (j = 0; j < pos; ++j)
283 bh = bh->b_this_page;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800284
285
286 if (unlikely(index == last_index))
287 lblock = end & mask;
288 else
289 lblock = blks_per_page;
290
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700291 do {
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800292 if (j >= lblock)
293 break;
294 pos = (i - beg) + j;
295
296 if (!buffer_mapped(bh))
297 map_bh(bh, inode->i_sb, oldb + pos);
298 if (!buffer_uptodate(bh)) {
299 ll_rw_block(READ, 1, &bh);
300 wait_on_buffer(bh);
301 if (!buffer_uptodate(bh)) {
Harvey Harrison97460772008-04-28 02:16:17 -0700302 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800303 "read of block failed\n");
304 break;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800305 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700306 }
307
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800308 UFSD(" change from %llu to %llu, pos %u\n",
Andrew Morton9df13032008-03-19 17:01:05 -0700309 (unsigned long long)(pos + oldb),
310 (unsigned long long)(pos + newb), pos);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800311
312 bh->b_blocknr = newb + pos;
313 unmap_underlying_metadata(bh->b_bdev,
314 bh->b_blocknr);
315 mark_buffer_dirty(bh);
316 ++j;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700317 bh = bh->b_this_page;
318 } while (bh != head);
319
Evgeniy Dushistov10e5dce2006-07-01 04:36:24 -0700320 if (likely(cur_index != index))
321 ufs_put_locked_page(page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700322 }
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700323 UFSD("EXIT\n");
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700324}
325
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800326static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
327 int sync)
328{
329 struct buffer_head *bh;
330 sector_t end = beg + n;
331
332 for (; beg < end; ++beg) {
333 bh = sb_getblk(inode->i_sb, beg);
334 lock_buffer(bh);
335 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
336 set_buffer_uptodate(bh);
337 mark_buffer_dirty(bh);
338 unlock_buffer(bh);
339 if (IS_SYNC(inode) || sync)
340 sync_dirty_buffer(bh);
341 brelse(bh);
342 }
343}
344
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800345u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
346 u64 goal, unsigned count, int *err,
347 struct page *locked_page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348{
349 struct super_block * sb;
350 struct ufs_sb_private_info * uspi;
351 struct ufs_super_block_first * usb1;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800352 unsigned cgno, oldcount, newcount;
353 u64 tmp, request, result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800355 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
356 inode->i_ino, (unsigned long long)fragment,
357 (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358
359 sb = inode->i_sb;
360 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300361 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362 *err = -ENOSPC;
363
364 lock_super (sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800365 tmp = ufs_data_ptr_to_cpu(sb, p);
366
Linus Torvalds1da177e2005-04-16 15:20:36 -0700367 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800368 ufs_warning(sb, "ufs_new_fragments", "internal warning"
369 " fragment %llu, count %u",
370 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371 count = uspi->s_fpb - ufs_fragnum(fragment);
372 }
373 oldcount = ufs_fragnum (fragment);
374 newcount = oldcount + count;
375
376 /*
377 * Somebody else has just allocated our fragments
378 */
379 if (oldcount) {
380 if (!tmp) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800381 ufs_error(sb, "ufs_new_fragments", "internal error, "
382 "fragment %llu, tmp %llu\n",
383 (unsigned long long)fragment,
384 (unsigned long long)tmp);
385 unlock_super(sb);
386 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387 }
388 if (fragment < UFS_I(inode)->i_lastfrag) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700389 UFSD("EXIT (ALREADY ALLOCATED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 unlock_super (sb);
391 return 0;
392 }
393 }
394 else {
395 if (tmp) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700396 UFSD("EXIT (ALREADY ALLOCATED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700397 unlock_super(sb);
398 return 0;
399 }
400 }
401
402 /*
403 * There is not enough space for user on the device
404 */
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700405 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700407 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 return 0;
409 }
410
411 if (goal >= uspi->s_size)
412 goal = 0;
413 if (goal == 0)
414 cgno = ufs_inotocg (inode->i_ino);
415 else
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800416 cgno = ufs_dtog(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417
418 /*
419 * allocate new fragment
420 */
421 if (oldcount == 0) {
422 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
423 if (result) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800424 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425 *err = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800426 UFS_I(inode)->i_lastfrag =
Dan Carpenter1d582722011-05-26 16:25:12 -0700427 max(UFS_I(inode)->i_lastfrag, fragment + count);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800428 ufs_clear_frags(inode, result + oldcount,
429 newcount - oldcount, locked_page != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700430 }
431 unlock_super(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800432 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 return result;
434 }
435
436 /*
437 * resize block
438 */
439 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
440 if (result) {
441 *err = 0;
Dan Carpenter1d582722011-05-26 16:25:12 -0700442 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
443 fragment + count);
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800444 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
445 locked_page != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446 unlock_super(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800447 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448 return result;
449 }
450
451 /*
452 * allocate new block and move data
453 */
454 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
455 case UFS_OPTSPACE:
456 request = newcount;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700457 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
458 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459 break;
460 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
461 break;
462 default:
463 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
464
465 case UFS_OPTTIME:
466 request = uspi->s_fpb;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700467 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468 (uspi->s_minfree - 2) / 100)
469 break;
470 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
471 break;
472 }
473 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
474 if (result) {
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800475 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
476 locked_page != NULL);
Evgeniy Dushistov4b25a372007-03-16 13:38:09 -0800477 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
478 uspi->s_sbbase + tmp,
479 uspi->s_sbbase + result, locked_page);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800480 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481 *err = 0;
Dan Carpenter1d582722011-05-26 16:25:12 -0700482 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
483 fragment + count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 unlock_super(sb);
485 if (newcount < request)
486 ufs_free_fragments (inode, result + newcount, request - newcount);
487 ufs_free_fragments (inode, tmp, oldcount);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800488 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489 return result;
490 }
491
492 unlock_super(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700493 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494 return 0;
495}
496
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800497static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
498 unsigned oldcount, unsigned newcount, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700499{
500 struct super_block * sb;
501 struct ufs_sb_private_info * uspi;
502 struct ufs_super_block_first * usb1;
503 struct ufs_cg_private_info * ucpi;
504 struct ufs_cylinder_group * ucg;
505 unsigned cgno, fragno, fragoff, count, fragsize, i;
506
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800507 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
508 (unsigned long long)fragment, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700509
510 sb = inode->i_sb;
511 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300512 usb1 = ubh_get_usb_first (uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 count = newcount - oldcount;
514
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800515 cgno = ufs_dtog(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
517 return 0;
518 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
519 return 0;
520 ucpi = ufs_load_cylinder (sb, cgno);
521 if (!ucpi)
522 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700523 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524 if (!ufs_cg_chkmagic(sb, ucg)) {
525 ufs_panic (sb, "ufs_add_fragments",
526 "internal error, bad magic number on cg %u", cgno);
527 return 0;
528 }
529
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800530 fragno = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531 fragoff = ufs_fragnum (fragno);
532 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700533 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534 return 0;
535 /*
536 * Block can be extended
537 */
538 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
539 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700540 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541 break;
542 fragsize = i - oldcount;
543 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
544 ufs_panic (sb, "ufs_add_fragments",
545 "internal error or corrupted bitmap on cg %u", cgno);
546 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
547 if (fragsize != count)
548 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
549 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700550 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700551
552 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
553 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700554 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700556 ubh_mark_buffer_dirty (USPI_UBH(uspi));
557 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200558 if (sb->s_flags & MS_SYNCHRONOUS)
559 ubh_sync_block(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560 sb->s_dirt = 1;
561
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800562 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700563
564 return fragment;
565}
566
567#define UFS_TEST_FREE_SPACE_CG \
568 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
569 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
570 goto cg_found; \
571 for (k = count; k < uspi->s_fpb; k++) \
572 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
573 goto cg_found;
574
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800575static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
576 u64 goal, unsigned count, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577{
578 struct super_block * sb;
579 struct ufs_sb_private_info * uspi;
580 struct ufs_super_block_first * usb1;
581 struct ufs_cg_private_info * ucpi;
582 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800583 unsigned oldcg, i, j, k, allocsize;
584 u64 result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800586 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
587 inode->i_ino, cgno, (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700588
589 sb = inode->i_sb;
590 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300591 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700592 oldcg = cgno;
593
594 /*
595 * 1. searching on preferred cylinder group
596 */
597 UFS_TEST_FREE_SPACE_CG
598
599 /*
600 * 2. quadratic rehash
601 */
602 for (j = 1; j < uspi->s_ncg; j *= 2) {
603 cgno += j;
604 if (cgno >= uspi->s_ncg)
605 cgno -= uspi->s_ncg;
606 UFS_TEST_FREE_SPACE_CG
607 }
608
609 /*
610 * 3. brute force search
611 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
612 */
613 cgno = (oldcg + 1) % uspi->s_ncg;
614 for (j = 2; j < uspi->s_ncg; j++) {
615 cgno++;
616 if (cgno >= uspi->s_ncg)
617 cgno = 0;
618 UFS_TEST_FREE_SPACE_CG
619 }
620
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700621 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622 return 0;
623
624cg_found:
625 ucpi = ufs_load_cylinder (sb, cgno);
626 if (!ucpi)
627 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700628 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629 if (!ufs_cg_chkmagic(sb, ucg))
630 ufs_panic (sb, "ufs_alloc_fragments",
631 "internal error, bad magic number on cg %u", cgno);
632 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
633
634 if (count == uspi->s_fpb) {
635 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800636 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637 return 0;
638 goto succed;
639 }
640
641 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
642 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
643 break;
644
645 if (allocsize == uspi->s_fpb) {
646 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800647 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 return 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800649 goal = ufs_dtogd(uspi, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700650 for (i = count; i < uspi->s_fpb; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700651 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652 i = uspi->s_fpb - count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653
654 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700655 uspi->cs_total.cs_nffree += i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
657 fs32_add(sb, &ucg->cg_frsum[i], 1);
658 goto succed;
659 }
660
661 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800662 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664 for (i = 0; i < count; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700665 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666
667 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700668 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700669 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
670 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
671
672 if (count != allocsize)
673 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
674
675succed:
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700676 ubh_mark_buffer_dirty (USPI_UBH(uspi));
677 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200678 if (sb->s_flags & MS_SYNCHRONOUS)
679 ubh_sync_block(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 sb->s_dirt = 1;
681
682 result += cgno * uspi->s_fpg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800683 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700684 return result;
685}
686
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800687static u64 ufs_alloccg_block(struct inode *inode,
688 struct ufs_cg_private_info *ucpi,
689 u64 goal, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700690{
691 struct super_block * sb;
692 struct ufs_sb_private_info * uspi;
693 struct ufs_super_block_first * usb1;
694 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800695 u64 result, blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700696
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800697 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700698
699 sb = inode->i_sb;
700 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300701 usb1 = ubh_get_usb_first(uspi);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700702 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700703
704 if (goal == 0) {
705 goal = ucpi->c_rotor;
706 goto norot;
707 }
708 goal = ufs_blknum (goal);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800709 goal = ufs_dtogd(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710
711 /*
712 * If the requested block is available, use it.
713 */
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700714 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715 result = goal;
716 goto gotit;
717 }
718
719norot:
720 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800721 if (result == INVBLOCK)
722 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700723 ucpi->c_rotor = result;
724gotit:
725 blkno = ufs_fragstoblks(result);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700726 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700727 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
728 ufs_clusteracct (sb, ucpi, blkno, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729
730 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700731 uspi->cs_total.cs_nbfree--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800733
734 if (uspi->fs_magic != UFS2_MAGIC) {
735 unsigned cylno = ufs_cbtocylno((unsigned)result);
736
737 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
738 ufs_cbtorpos((unsigned)result)), 1);
739 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
740 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800742 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700743
744 return result;
745}
746
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700747static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
748 struct ufs_buffer_head *ubh,
749 unsigned begin, unsigned size,
750 unsigned char *table, unsigned char mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751{
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700752 unsigned rest, offset;
753 unsigned char *cp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700754
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700756 offset = begin & ~uspi->s_fmask;
757 begin >>= uspi->s_fshift;
758 for (;;) {
759 if ((offset + size) < uspi->s_fsize)
760 rest = size;
761 else
762 rest = uspi->s_fsize - offset;
763 size -= rest;
764 cp = ubh->bh[begin]->b_data + offset;
765 while ((table[*cp++] & mask) == 0 && --rest)
766 ;
767 if (rest || !size)
768 break;
769 begin++;
770 offset = 0;
771 }
772 return (size + rest);
773}
774
775/*
776 * Find a block of the specified size in the specified cylinder group.
777 * @sp: pointer to super block
778 * @ucpi: pointer to cylinder group info
779 * @goal: near which block we want find new one
780 * @count: specified size
781 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800782static u64 ufs_bitmap_search(struct super_block *sb,
783 struct ufs_cg_private_info *ucpi,
784 u64 goal, unsigned count)
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700785{
786 /*
787 * Bit patterns for identifying fragments in the block map
788 * used as ((map & mask_arr) == want_arr)
789 */
790 static const int mask_arr[9] = {
791 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
792 };
793 static const int want_arr[9] = {
794 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
795 };
796 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
797 struct ufs_super_block_first *usb1;
798 struct ufs_cylinder_group *ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800799 unsigned start, length, loc;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700800 unsigned pos, want, blockmap, mask, end;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800801 u64 result;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700802
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800803 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
804 (unsigned long long)goal, count);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700805
Evgeniy7b4ee732006-01-14 11:42:06 +0300806 usb1 = ubh_get_usb_first (uspi);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700807 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700808
809 if (goal)
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800810 start = ufs_dtogd(uspi, goal) >> 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700811 else
812 start = ucpi->c_frotor >> 3;
813
814 length = ((uspi->s_fpg + 7) >> 3) - start;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700815 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700816 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
817 1 << (count - 1 + (uspi->s_fpb & 7)));
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700818 if (loc == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819 length = start + 1;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700820 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
821 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
822 ufs_fragtable_other,
823 1 << (count - 1 + (uspi->s_fpb & 7)));
824 if (loc == 0) {
825 ufs_error(sb, "ufs_bitmap_search",
826 "bitmap corrupted on cg %u, start %u,"
827 " length %u, count %u, freeoff %u\n",
828 ucpi->c_cgx, start, length, count,
829 ucpi->c_freeoff);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800830 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831 }
832 start = 0;
833 }
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700834 result = (start + length - loc) << 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835 ucpi->c_frotor = result;
836
837 /*
838 * found the byte in the map
839 */
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700840
841 for (end = result + 8; result < end; result += uspi->s_fpb) {
842 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
843 blockmap <<= 1;
844 mask = mask_arr[count];
845 want = want_arr[count];
846 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
847 if ((blockmap & mask) == want) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800848 UFSD("EXIT, result %llu\n",
849 (unsigned long long)result);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700850 return result + pos;
851 }
852 mask <<= 1;
853 want <<= 1;
854 }
855 }
856
857 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
858 ucpi->c_cgx);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700859 UFSD("EXIT (FAILED)\n");
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800860 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700861}
862
863static void ufs_clusteracct(struct super_block * sb,
864 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
865{
866 struct ufs_sb_private_info * uspi;
867 int i, start, end, forw, back;
868
869 uspi = UFS_SB(sb)->s_uspi;
870 if (uspi->s_contigsumsize <= 0)
871 return;
872
873 if (cnt > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700874 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 else
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700876 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700877
878 /*
879 * Find the size of the cluster going forward.
880 */
881 start = blkno + 1;
882 end = start + uspi->s_contigsumsize;
883 if ( end >= ucpi->c_nclusterblks)
884 end = ucpi->c_nclusterblks;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700885 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886 if (i > end)
887 i = end;
888 forw = i - start;
889
890 /*
891 * Find the size of the cluster going backward.
892 */
893 start = blkno - 1;
894 end = start - uspi->s_contigsumsize;
895 if (end < 0 )
896 end = -1;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700897 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898 if ( i < end)
899 i = end;
900 back = start - i;
901
902 /*
903 * Account for old cluster and the possibly new forward and
904 * back clusters.
905 */
906 i = back + forw + 1;
907 if (i > uspi->s_contigsumsize)
908 i = uspi->s_contigsumsize;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700909 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910 if (back > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700911 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912 if (forw > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700913 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914}
915
916
917static unsigned char ufs_fragtable_8fpb[] = {
918 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
919 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
920 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
921 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
922 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
923 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
924 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
925 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
926 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
927 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
928 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
929 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
930 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
931 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
932 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
933 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
934};
935
936static unsigned char ufs_fragtable_other[] = {
937 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
938 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
939 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
940 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
941 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
942 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
943 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
944 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
945 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
946 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
947 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
948 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
949 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
950 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
951 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
952 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
953};