blob: 54c16ec95dfff52ff9113f0b61ab50d602bd58f9 [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>
15#include <linux/quotaops.h>
16#include <linux/buffer_head.h>
Randy Dunlap16f7e0f2006-01-11 12:17:46 -080017#include <linux/capability.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include <linux/bitops.h>
19#include <asm/byteorder.h>
20
Mike Frysingere5420592008-02-08 04:21:31 -080021#include "ufs_fs.h"
Christoph Hellwigbcd6d4e2007-10-16 23:26:51 -070022#include "ufs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070023#include "swab.h"
24#include "util.h"
25
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080026#define INVBLOCK ((u64)-1L)
27
28static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned, int *);
29static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);
30static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);
31static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);
Linus Torvalds1da177e2005-04-16 15:20:36 -070032static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
33static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
34
35/*
36 * Free 'count' fragments from fragment number 'fragment'
37 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080038void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -070039{
Linus Torvalds1da177e2005-04-16 15:20:36 -070040 struct super_block * sb;
41 struct ufs_sb_private_info * uspi;
42 struct ufs_super_block_first * usb1;
43 struct ufs_cg_private_info * ucpi;
44 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080045 unsigned cgno, bit, end_bit, bbase, blkmap, i;
46 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -070047
48 sb = inode->i_sb;
49 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +030050 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -070051
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080052 UFSD("ENTER, fragment %llu, count %u\n",
53 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -070054
55 if (ufs_fragnum(fragment) + count > uspi->s_fpg)
56 ufs_error (sb, "ufs_free_fragments", "internal error");
57
58 lock_super(sb);
59
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080060 cgno = ufs_dtog(uspi, fragment);
61 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -070062 if (cgno >= uspi->s_ncg) {
63 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
64 goto failed;
65 }
66
67 ucpi = ufs_load_cylinder (sb, cgno);
68 if (!ucpi)
69 goto failed;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070070 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -070071 if (!ufs_cg_chkmagic(sb, ucg)) {
72 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
73 goto failed;
74 }
75
76 end_bit = bit + count;
77 bbase = ufs_blknum (bit);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070078 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
80 for (i = bit; i < end_bit; i++) {
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070081 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, i))
82 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);
Evgeniy7b4ee732006-01-14 11:42:06 +030083 else
84 ufs_error (sb, "ufs_free_fragments",
85 "bit already cleared for fragment %u", i);
Linus Torvalds1da177e2005-04-16 15:20:36 -070086 }
87
Jan Kara5f5fa792009-01-26 17:15:30 +010088 vfs_dq_free_block(inode, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
90
91 fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -070092 uspi->cs_total.cs_nffree += count;
Linus Torvalds1da177e2005-04-16 15:20:36 -070093 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070094 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070095 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
96
97 /*
98 * Trying to reassemble free fragments into block
99 */
100 blkno = ufs_fragstoblks (bbase);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700101 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700103 uspi->cs_total.cs_nffree -= uspi->s_fpb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700104 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
105 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
106 ufs_clusteracct (sb, ucpi, blkno, 1);
107 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700108 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800110 if (uspi->fs_magic != UFS2_MAGIC) {
111 unsigned cylno = ufs_cbtocylno (bbase);
112
113 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
114 ufs_cbtorpos(bbase)), 1);
115 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
116 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700117 }
118
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700119 ubh_mark_buffer_dirty (USPI_UBH(uspi));
120 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 if (sb->s_flags & MS_SYNCHRONOUS) {
Evgeniy Dushistov098d5af2006-06-25 05:47:31 -0700122 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700123 ubh_wait_on_buffer (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124 }
125 sb->s_dirt = 1;
126
127 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700128 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129 return;
130
131failed:
132 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700133 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134 return;
135}
136
137/*
138 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
139 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800140void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700141{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142 struct super_block * sb;
143 struct ufs_sb_private_info * uspi;
144 struct ufs_super_block_first * usb1;
145 struct ufs_cg_private_info * ucpi;
146 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800147 unsigned overflow, cgno, bit, end_bit, i;
148 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
150 sb = inode->i_sb;
151 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300152 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800154 UFSD("ENTER, fragment %llu, count %u\n",
155 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156
157 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
158 ufs_error (sb, "ufs_free_blocks", "internal error, "
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800159 "fragment %llu, count %u\n",
160 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161 goto failed;
162 }
163
164 lock_super(sb);
165
166do_more:
167 overflow = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800168 cgno = ufs_dtog(uspi, fragment);
169 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700170 if (cgno >= uspi->s_ncg) {
171 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700172 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173 }
174 end_bit = bit + count;
175 if (end_bit > uspi->s_fpg) {
176 overflow = bit + count - uspi->s_fpg;
177 count -= overflow;
178 end_bit -= overflow;
179 }
180
181 ucpi = ufs_load_cylinder (sb, cgno);
182 if (!ucpi)
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700183 goto failed_unlock;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700184 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185 if (!ufs_cg_chkmagic(sb, ucg)) {
186 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700187 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188 }
189
190 for (i = bit; i < end_bit; i += uspi->s_fpb) {
191 blkno = ufs_fragstoblks(i);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700192 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193 ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
194 }
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700195 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
197 ufs_clusteracct (sb, ucpi, blkno, 1);
Jan Kara5f5fa792009-01-26 17:15:30 +0100198 vfs_dq_free_block(inode, uspi->s_fpb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199
200 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700201 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800203
204 if (uspi->fs_magic != UFS2_MAGIC) {
205 unsigned cylno = ufs_cbtocylno(i);
206
207 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
208 ufs_cbtorpos(i)), 1);
209 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
210 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 }
212
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700213 ubh_mark_buffer_dirty (USPI_UBH(uspi));
214 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 if (sb->s_flags & MS_SYNCHRONOUS) {
Evgeniy Dushistov098d5af2006-06-25 05:47:31 -0700216 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700217 ubh_wait_on_buffer (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218 }
219
220 if (overflow) {
221 fragment += count;
222 count = overflow;
223 goto do_more;
224 }
225
226 sb->s_dirt = 1;
227 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700228 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 return;
230
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700231failed_unlock:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232 unlock_super (sb);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700233failed:
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700234 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235 return;
236}
237
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700238/*
239 * Modify inode page cache in such way:
240 * have - blocks with b_blocknr equal to oldb...oldb+count-1
241 * get - blocks with b_blocknr equal to newb...newb+count-1
242 * also we suppose that oldb...oldb+count-1 blocks
243 * situated at the end of file.
244 *
245 * We can come here from ufs_writepage or ufs_prepare_write,
246 * locked_page is argument of these functions, so we already lock it.
247 */
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800248static void ufs_change_blocknr(struct inode *inode, sector_t beg,
249 unsigned int count, sector_t oldb,
250 sector_t newb, struct page *locked_page)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700251{
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800252 const unsigned blks_per_page =
253 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
254 const unsigned mask = blks_per_page - 1;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800255 struct address_space * const mapping = inode->i_mapping;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800256 pgoff_t index, cur_index, last_index;
257 unsigned pos, j, lblock;
258 sector_t end, i;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700259 struct page *page;
260 struct buffer_head *head, *bh;
261
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800262 UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",
263 inode->i_ino, count,
264 (unsigned long long)oldb, (unsigned long long)newb);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700265
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800266 BUG_ON(!locked_page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700267 BUG_ON(!PageLocked(locked_page));
268
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800269 cur_index = locked_page->index;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800270 end = count + beg;
271 last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
272 for (i = beg; i < end; i = (i | mask) + 1) {
273 index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700274
275 if (likely(cur_index != index)) {
276 page = ufs_get_locked_page(mapping, index);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800277 if (!page)/* it was truncated */
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700278 continue;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800279 if (IS_ERR(page)) {/* or EIO */
Harvey Harrison97460772008-04-28 02:16:17 -0700280 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800281 "read of page %llu failed\n",
282 (unsigned long long)index);
283 continue;
284 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700285 } else
286 page = locked_page;
287
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700288 head = page_buffers(page);
289 bh = head;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800290 pos = i & mask;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800291 for (j = 0; j < pos; ++j)
292 bh = bh->b_this_page;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800293
294
295 if (unlikely(index == last_index))
296 lblock = end & mask;
297 else
298 lblock = blks_per_page;
299
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700300 do {
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800301 if (j >= lblock)
302 break;
303 pos = (i - beg) + j;
304
305 if (!buffer_mapped(bh))
306 map_bh(bh, inode->i_sb, oldb + pos);
307 if (!buffer_uptodate(bh)) {
308 ll_rw_block(READ, 1, &bh);
309 wait_on_buffer(bh);
310 if (!buffer_uptodate(bh)) {
Harvey Harrison97460772008-04-28 02:16:17 -0700311 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800312 "read of block failed\n");
313 break;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800314 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700315 }
316
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800317 UFSD(" change from %llu to %llu, pos %u\n",
Andrew Morton9df13032008-03-19 17:01:05 -0700318 (unsigned long long)(pos + oldb),
319 (unsigned long long)(pos + newb), pos);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800320
321 bh->b_blocknr = newb + pos;
322 unmap_underlying_metadata(bh->b_bdev,
323 bh->b_blocknr);
324 mark_buffer_dirty(bh);
325 ++j;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700326 bh = bh->b_this_page;
327 } while (bh != head);
328
Evgeniy Dushistov10e5dce2006-07-01 04:36:24 -0700329 if (likely(cur_index != index))
330 ufs_put_locked_page(page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700331 }
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700332 UFSD("EXIT\n");
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700333}
334
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800335static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
336 int sync)
337{
338 struct buffer_head *bh;
339 sector_t end = beg + n;
340
341 for (; beg < end; ++beg) {
342 bh = sb_getblk(inode->i_sb, beg);
343 lock_buffer(bh);
344 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
345 set_buffer_uptodate(bh);
346 mark_buffer_dirty(bh);
347 unlock_buffer(bh);
348 if (IS_SYNC(inode) || sync)
349 sync_dirty_buffer(bh);
350 brelse(bh);
351 }
352}
353
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800354u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
355 u64 goal, unsigned count, int *err,
356 struct page *locked_page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357{
358 struct super_block * sb;
359 struct ufs_sb_private_info * uspi;
360 struct ufs_super_block_first * usb1;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800361 unsigned cgno, oldcount, newcount;
362 u64 tmp, request, result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800364 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
365 inode->i_ino, (unsigned long long)fragment,
366 (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700367
368 sb = inode->i_sb;
369 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300370 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371 *err = -ENOSPC;
372
373 lock_super (sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800374 tmp = ufs_data_ptr_to_cpu(sb, p);
375
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800377 ufs_warning(sb, "ufs_new_fragments", "internal warning"
378 " fragment %llu, count %u",
379 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700380 count = uspi->s_fpb - ufs_fragnum(fragment);
381 }
382 oldcount = ufs_fragnum (fragment);
383 newcount = oldcount + count;
384
385 /*
386 * Somebody else has just allocated our fragments
387 */
388 if (oldcount) {
389 if (!tmp) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800390 ufs_error(sb, "ufs_new_fragments", "internal error, "
391 "fragment %llu, tmp %llu\n",
392 (unsigned long long)fragment,
393 (unsigned long long)tmp);
394 unlock_super(sb);
395 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 }
397 if (fragment < UFS_I(inode)->i_lastfrag) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700398 UFSD("EXIT (ALREADY ALLOCATED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399 unlock_super (sb);
400 return 0;
401 }
402 }
403 else {
404 if (tmp) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700405 UFSD("EXIT (ALREADY ALLOCATED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 unlock_super(sb);
407 return 0;
408 }
409 }
410
411 /*
412 * There is not enough space for user on the device
413 */
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700414 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 unlock_super (sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700416 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417 return 0;
418 }
419
420 if (goal >= uspi->s_size)
421 goal = 0;
422 if (goal == 0)
423 cgno = ufs_inotocg (inode->i_ino);
424 else
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800425 cgno = ufs_dtog(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426
427 /*
428 * allocate new fragment
429 */
430 if (oldcount == 0) {
431 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
432 if (result) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800433 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700434 *err = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800435 UFS_I(inode)->i_lastfrag =
436 max_t(u32, UFS_I(inode)->i_lastfrag,
437 fragment + count);
438 ufs_clear_frags(inode, result + oldcount,
439 newcount - oldcount, locked_page != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700440 }
441 unlock_super(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800442 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 return result;
444 }
445
446 /*
447 * resize block
448 */
449 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
450 if (result) {
451 *err = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800453 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
454 locked_page != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455 unlock_super(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800456 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700457 return result;
458 }
459
460 /*
461 * allocate new block and move data
462 */
463 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
464 case UFS_OPTSPACE:
465 request = newcount;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700466 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
467 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468 break;
469 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
470 break;
471 default:
472 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
473
474 case UFS_OPTTIME:
475 request = uspi->s_fpb;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700476 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 (uspi->s_minfree - 2) / 100)
478 break;
479 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
480 break;
481 }
482 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
483 if (result) {
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800484 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
485 locked_page != NULL);
Evgeniy Dushistov4b25a372007-03-16 13:38:09 -0800486 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
487 uspi->s_sbbase + tmp,
488 uspi->s_sbbase + result, locked_page);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800489 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490 *err = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 unlock_super(sb);
493 if (newcount < request)
494 ufs_free_fragments (inode, result + newcount, request - newcount);
495 ufs_free_fragments (inode, tmp, oldcount);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800496 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497 return result;
498 }
499
500 unlock_super(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700501 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 return 0;
503}
504
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800505static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
506 unsigned oldcount, unsigned newcount, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700507{
508 struct super_block * sb;
509 struct ufs_sb_private_info * uspi;
510 struct ufs_super_block_first * usb1;
511 struct ufs_cg_private_info * ucpi;
512 struct ufs_cylinder_group * ucg;
513 unsigned cgno, fragno, fragoff, count, fragsize, i;
514
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800515 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
516 (unsigned long long)fragment, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700517
518 sb = inode->i_sb;
519 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300520 usb1 = ubh_get_usb_first (uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700521 count = newcount - oldcount;
522
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800523 cgno = ufs_dtog(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
525 return 0;
526 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
527 return 0;
528 ucpi = ufs_load_cylinder (sb, cgno);
529 if (!ucpi)
530 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700531 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 if (!ufs_cg_chkmagic(sb, ucg)) {
533 ufs_panic (sb, "ufs_add_fragments",
534 "internal error, bad magic number on cg %u", cgno);
535 return 0;
536 }
537
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800538 fragno = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700539 fragoff = ufs_fragnum (fragno);
540 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700541 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542 return 0;
543 /*
544 * Block can be extended
545 */
546 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
547 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700548 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 break;
550 fragsize = i - oldcount;
551 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
552 ufs_panic (sb, "ufs_add_fragments",
553 "internal error or corrupted bitmap on cg %u", cgno);
554 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
555 if (fragsize != count)
556 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
557 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700558 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
Jan Kara5f5fa792009-01-26 17:15:30 +0100559 if (vfs_dq_alloc_block(inode, count)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560 *err = -EDQUOT;
561 return 0;
562 }
563
564 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
565 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700566 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700568 ubh_mark_buffer_dirty (USPI_UBH(uspi));
569 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570 if (sb->s_flags & MS_SYNCHRONOUS) {
Evgeniy Dushistov098d5af2006-06-25 05:47:31 -0700571 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700572 ubh_wait_on_buffer (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700573 }
574 sb->s_dirt = 1;
575
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800576 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
578 return fragment;
579}
580
581#define UFS_TEST_FREE_SPACE_CG \
582 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
583 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
584 goto cg_found; \
585 for (k = count; k < uspi->s_fpb; k++) \
586 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
587 goto cg_found;
588
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800589static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
590 u64 goal, unsigned count, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591{
592 struct super_block * sb;
593 struct ufs_sb_private_info * uspi;
594 struct ufs_super_block_first * usb1;
595 struct ufs_cg_private_info * ucpi;
596 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800597 unsigned oldcg, i, j, k, allocsize;
598 u64 result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800600 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
601 inode->i_ino, cgno, (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602
603 sb = inode->i_sb;
604 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300605 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700606 oldcg = cgno;
607
608 /*
609 * 1. searching on preferred cylinder group
610 */
611 UFS_TEST_FREE_SPACE_CG
612
613 /*
614 * 2. quadratic rehash
615 */
616 for (j = 1; j < uspi->s_ncg; j *= 2) {
617 cgno += j;
618 if (cgno >= uspi->s_ncg)
619 cgno -= uspi->s_ncg;
620 UFS_TEST_FREE_SPACE_CG
621 }
622
623 /*
624 * 3. brute force search
625 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
626 */
627 cgno = (oldcg + 1) % uspi->s_ncg;
628 for (j = 2; j < uspi->s_ncg; j++) {
629 cgno++;
630 if (cgno >= uspi->s_ncg)
631 cgno = 0;
632 UFS_TEST_FREE_SPACE_CG
633 }
634
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700635 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636 return 0;
637
638cg_found:
639 ucpi = ufs_load_cylinder (sb, cgno);
640 if (!ucpi)
641 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700642 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643 if (!ufs_cg_chkmagic(sb, ucg))
644 ufs_panic (sb, "ufs_alloc_fragments",
645 "internal error, bad magic number on cg %u", cgno);
646 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
647
648 if (count == uspi->s_fpb) {
649 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800650 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651 return 0;
652 goto succed;
653 }
654
655 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
656 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
657 break;
658
659 if (allocsize == uspi->s_fpb) {
660 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800661 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 return 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800663 goal = ufs_dtogd(uspi, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664 for (i = count; i < uspi->s_fpb; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700665 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666 i = uspi->s_fpb - count;
Jan Kara5f5fa792009-01-26 17:15:30 +0100667 vfs_dq_free_block(inode, i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700668
669 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700670 uspi->cs_total.cs_nffree += i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
672 fs32_add(sb, &ucg->cg_frsum[i], 1);
673 goto succed;
674 }
675
676 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800677 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678 return 0;
Jan Kara5f5fa792009-01-26 17:15:30 +0100679 if (vfs_dq_alloc_block(inode, count)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 *err = -EDQUOT;
681 return 0;
682 }
683 for (i = 0; i < count; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700684 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685
686 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700687 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
689 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
690
691 if (count != allocsize)
692 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
693
694succed:
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700695 ubh_mark_buffer_dirty (USPI_UBH(uspi));
696 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697 if (sb->s_flags & MS_SYNCHRONOUS) {
Evgeniy Dushistov098d5af2006-06-25 05:47:31 -0700698 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700699 ubh_wait_on_buffer (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 }
701 sb->s_dirt = 1;
702
703 result += cgno * uspi->s_fpg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800704 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 return result;
706}
707
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800708static u64 ufs_alloccg_block(struct inode *inode,
709 struct ufs_cg_private_info *ucpi,
710 u64 goal, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700711{
712 struct super_block * sb;
713 struct ufs_sb_private_info * uspi;
714 struct ufs_super_block_first * usb1;
715 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800716 u64 result, blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800718 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700719
720 sb = inode->i_sb;
721 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300722 usb1 = ubh_get_usb_first(uspi);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700723 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700724
725 if (goal == 0) {
726 goal = ucpi->c_rotor;
727 goto norot;
728 }
729 goal = ufs_blknum (goal);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800730 goal = ufs_dtogd(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731
732 /*
733 * If the requested block is available, use it.
734 */
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700735 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 result = goal;
737 goto gotit;
738 }
739
740norot:
741 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800742 if (result == INVBLOCK)
743 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744 ucpi->c_rotor = result;
745gotit:
746 blkno = ufs_fragstoblks(result);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700747 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700748 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
749 ufs_clusteracct (sb, ucpi, blkno, -1);
Jan Kara5f5fa792009-01-26 17:15:30 +0100750 if (vfs_dq_alloc_block(inode, uspi->s_fpb)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751 *err = -EDQUOT;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800752 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700753 }
754
755 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700756 uspi->cs_total.cs_nbfree--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800758
759 if (uspi->fs_magic != UFS2_MAGIC) {
760 unsigned cylno = ufs_cbtocylno((unsigned)result);
761
762 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
763 ufs_cbtorpos((unsigned)result)), 1);
764 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
765 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700766
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800767 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700768
769 return result;
770}
771
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700772static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
773 struct ufs_buffer_head *ubh,
774 unsigned begin, unsigned size,
775 unsigned char *table, unsigned char mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776{
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700777 unsigned rest, offset;
778 unsigned char *cp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700779
Linus Torvalds1da177e2005-04-16 15:20:36 -0700780
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700781 offset = begin & ~uspi->s_fmask;
782 begin >>= uspi->s_fshift;
783 for (;;) {
784 if ((offset + size) < uspi->s_fsize)
785 rest = size;
786 else
787 rest = uspi->s_fsize - offset;
788 size -= rest;
789 cp = ubh->bh[begin]->b_data + offset;
790 while ((table[*cp++] & mask) == 0 && --rest)
791 ;
792 if (rest || !size)
793 break;
794 begin++;
795 offset = 0;
796 }
797 return (size + rest);
798}
799
800/*
801 * Find a block of the specified size in the specified cylinder group.
802 * @sp: pointer to super block
803 * @ucpi: pointer to cylinder group info
804 * @goal: near which block we want find new one
805 * @count: specified size
806 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800807static u64 ufs_bitmap_search(struct super_block *sb,
808 struct ufs_cg_private_info *ucpi,
809 u64 goal, unsigned count)
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700810{
811 /*
812 * Bit patterns for identifying fragments in the block map
813 * used as ((map & mask_arr) == want_arr)
814 */
815 static const int mask_arr[9] = {
816 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
817 };
818 static const int want_arr[9] = {
819 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
820 };
821 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
822 struct ufs_super_block_first *usb1;
823 struct ufs_cylinder_group *ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800824 unsigned start, length, loc;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700825 unsigned pos, want, blockmap, mask, end;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800826 u64 result;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700827
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800828 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
829 (unsigned long long)goal, count);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700830
Evgeniy7b4ee732006-01-14 11:42:06 +0300831 usb1 = ubh_get_usb_first (uspi);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700832 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833
834 if (goal)
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800835 start = ufs_dtogd(uspi, goal) >> 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 else
837 start = ucpi->c_frotor >> 3;
838
839 length = ((uspi->s_fpg + 7) >> 3) - start;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700840 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
842 1 << (count - 1 + (uspi->s_fpb & 7)));
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700843 if (loc == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844 length = start + 1;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700845 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
846 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
847 ufs_fragtable_other,
848 1 << (count - 1 + (uspi->s_fpb & 7)));
849 if (loc == 0) {
850 ufs_error(sb, "ufs_bitmap_search",
851 "bitmap corrupted on cg %u, start %u,"
852 " length %u, count %u, freeoff %u\n",
853 ucpi->c_cgx, start, length, count,
854 ucpi->c_freeoff);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800855 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700856 }
857 start = 0;
858 }
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700859 result = (start + length - loc) << 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860 ucpi->c_frotor = result;
861
862 /*
863 * found the byte in the map
864 */
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700865
866 for (end = result + 8; result < end; result += uspi->s_fpb) {
867 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
868 blockmap <<= 1;
869 mask = mask_arr[count];
870 want = want_arr[count];
871 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
872 if ((blockmap & mask) == want) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800873 UFSD("EXIT, result %llu\n",
874 (unsigned long long)result);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700875 return result + pos;
876 }
877 mask <<= 1;
878 want <<= 1;
879 }
880 }
881
882 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
883 ucpi->c_cgx);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700884 UFSD("EXIT (FAILED)\n");
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800885 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886}
887
888static void ufs_clusteracct(struct super_block * sb,
889 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
890{
891 struct ufs_sb_private_info * uspi;
892 int i, start, end, forw, back;
893
894 uspi = UFS_SB(sb)->s_uspi;
895 if (uspi->s_contigsumsize <= 0)
896 return;
897
898 if (cnt > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700899 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900 else
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700901 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902
903 /*
904 * Find the size of the cluster going forward.
905 */
906 start = blkno + 1;
907 end = start + uspi->s_contigsumsize;
908 if ( end >= ucpi->c_nclusterblks)
909 end = ucpi->c_nclusterblks;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700910 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700911 if (i > end)
912 i = end;
913 forw = i - start;
914
915 /*
916 * Find the size of the cluster going backward.
917 */
918 start = blkno - 1;
919 end = start - uspi->s_contigsumsize;
920 if (end < 0 )
921 end = -1;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700922 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700923 if ( i < end)
924 i = end;
925 back = start - i;
926
927 /*
928 * Account for old cluster and the possibly new forward and
929 * back clusters.
930 */
931 i = back + forw + 1;
932 if (i > uspi->s_contigsumsize)
933 i = uspi->s_contigsumsize;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700934 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700935 if (back > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700936 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937 if (forw > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700938 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939}
940
941
942static unsigned char ufs_fragtable_8fpb[] = {
943 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
944 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
945 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
946 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
947 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
948 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
949 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
950 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
951 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
952 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
953 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
954 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
955 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
956 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
957 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
958 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
959};
960
961static unsigned char ufs_fragtable_other[] = {
962 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
963 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
964 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
965 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
966 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
967 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
968 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
969 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
970 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
971 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
972 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
973 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
974 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
975 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
976 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
977 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
978};