blob: 2c1036080d5276bcb51314e649e45f0d6f0990a5 [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
Fabian Frederick45641c82014-06-06 14:36:33 -070027static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080028static 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -070041 struct ufs_cg_private_info * ucpi;
42 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080043 unsigned cgno, bit, end_bit, bbase, blkmap, i;
44 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -070045
46 sb = inode->i_sb;
47 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -070048
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080049 UFSD("ENTER, fragment %llu, count %u\n",
50 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -070051
52 if (ufs_fragnum(fragment) + count > uspi->s_fpg)
53 ufs_error (sb, "ufs_free_fragments", "internal error");
54
Fabian Frederick02447562014-06-06 14:38:34 -070055 lock_ufs(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -070056
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -080057 cgno = ufs_dtog(uspi, fragment);
58 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -070059 if (cgno >= uspi->s_ncg) {
60 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
61 goto failed;
62 }
63
64 ucpi = ufs_load_cylinder (sb, cgno);
65 if (!ucpi)
66 goto failed;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070067 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -070068 if (!ufs_cg_chkmagic(sb, ucg)) {
69 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
70 goto failed;
71 }
72
73 end_bit = bit + count;
74 bbase = ufs_blknum (bit);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070075 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070076 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
77 for (i = bit; i < end_bit; i++) {
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070078 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, i))
79 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);
Evgeniy7b4ee732006-01-14 11:42:06 +030080 else
81 ufs_error (sb, "ufs_free_fragments",
82 "bit already cleared for fragment %u", i);
Linus Torvalds1da177e2005-04-16 15:20:36 -070083 }
84
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -070086 uspi->cs_total.cs_nffree += count;
Linus Torvalds1da177e2005-04-16 15:20:36 -070087 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070088 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
Linus Torvalds1da177e2005-04-16 15:20:36 -070089 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
90
91 /*
92 * Trying to reassemble free fragments into block
93 */
94 blkno = ufs_fragstoblks (bbase);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -070095 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070096 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -070097 uspi->cs_total.cs_nffree -= uspi->s_fpb;
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
99 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
100 ufs_clusteracct (sb, ucpi, blkno, 1);
101 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700102 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800104 if (uspi->fs_magic != UFS2_MAGIC) {
105 unsigned cylno = ufs_cbtocylno (bbase);
106
107 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
108 ufs_cbtorpos(bbase)), 1);
109 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
110 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700111 }
112
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700113 ubh_mark_buffer_dirty (USPI_UBH(uspi));
114 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200115 if (sb->s_flags & MS_SYNCHRONOUS)
116 ubh_sync_block(UCPI_UBH(ucpi));
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300117 ufs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118
Fabian Frederick02447562014-06-06 14:38:34 -0700119 unlock_ufs(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700120 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 return;
122
123failed:
Fabian Frederick02447562014-06-06 14:38:34 -0700124 unlock_ufs(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700125 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126 return;
127}
128
129/*
130 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
131 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800132void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700133{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134 struct super_block * sb;
135 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136 struct ufs_cg_private_info * ucpi;
137 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800138 unsigned overflow, cgno, bit, end_bit, i;
139 u64 blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140
141 sb = inode->i_sb;
142 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800144 UFSD("ENTER, fragment %llu, count %u\n",
145 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
147 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
148 ufs_error (sb, "ufs_free_blocks", "internal error, "
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800149 "fragment %llu, count %u\n",
150 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151 goto failed;
152 }
153
Fabian Frederick02447562014-06-06 14:38:34 -0700154 lock_ufs(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155
156do_more:
157 overflow = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800158 cgno = ufs_dtog(uspi, fragment);
159 bit = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160 if (cgno >= uspi->s_ncg) {
161 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700162 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163 }
164 end_bit = bit + count;
165 if (end_bit > uspi->s_fpg) {
166 overflow = bit + count - uspi->s_fpg;
167 count -= overflow;
168 end_bit -= overflow;
169 }
170
171 ucpi = ufs_load_cylinder (sb, cgno);
172 if (!ucpi)
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700173 goto failed_unlock;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700174 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175 if (!ufs_cg_chkmagic(sb, ucg)) {
176 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700177 goto failed_unlock;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178 }
179
180 for (i = bit; i < end_bit; i += uspi->s_fpb) {
181 blkno = ufs_fragstoblks(i);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700182 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700183 ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
184 }
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700185 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
187 ufs_clusteracct (sb, ucpi, blkno, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188
189 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700190 uspi->cs_total.cs_nbfree++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800192
193 if (uspi->fs_magic != UFS2_MAGIC) {
194 unsigned cylno = ufs_cbtocylno(i);
195
196 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
197 ufs_cbtorpos(i)), 1);
198 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
199 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200 }
201
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700202 ubh_mark_buffer_dirty (USPI_UBH(uspi));
203 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200204 if (sb->s_flags & MS_SYNCHRONOUS)
205 ubh_sync_block(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206
207 if (overflow) {
208 fragment += count;
209 count = overflow;
210 goto do_more;
211 }
212
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300213 ufs_mark_sb_dirty(sb);
Fabian Frederick02447562014-06-06 14:38:34 -0700214 unlock_ufs(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700215 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 return;
217
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700218failed_unlock:
Fabian Frederick02447562014-06-06 14:38:34 -0700219 unlock_ufs(sb);
Evgeniy Dushistov2e006392006-06-25 05:47:26 -0700220failed:
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700221 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222 return;
223}
224
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700225/*
226 * Modify inode page cache in such way:
227 * have - blocks with b_blocknr equal to oldb...oldb+count-1
228 * get - blocks with b_blocknr equal to newb...newb+count-1
229 * also we suppose that oldb...oldb+count-1 blocks
230 * situated at the end of file.
231 *
232 * We can come here from ufs_writepage or ufs_prepare_write,
233 * locked_page is argument of these functions, so we already lock it.
234 */
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800235static void ufs_change_blocknr(struct inode *inode, sector_t beg,
236 unsigned int count, sector_t oldb,
237 sector_t newb, struct page *locked_page)
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700238{
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800239 const unsigned blks_per_page =
240 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
241 const unsigned mask = blks_per_page - 1;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800242 struct address_space * const mapping = inode->i_mapping;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800243 pgoff_t index, cur_index, last_index;
244 unsigned pos, j, lblock;
245 sector_t end, i;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700246 struct page *page;
247 struct buffer_head *head, *bh;
248
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800249 UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",
250 inode->i_ino, count,
251 (unsigned long long)oldb, (unsigned long long)newb);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700252
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800253 BUG_ON(!locked_page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700254 BUG_ON(!PageLocked(locked_page));
255
Evgeniy Dushistova685e262007-01-29 13:19:54 -0800256 cur_index = locked_page->index;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800257 end = count + beg;
258 last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
259 for (i = beg; i < end; i = (i | mask) + 1) {
260 index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700261
262 if (likely(cur_index != index)) {
263 page = ufs_get_locked_page(mapping, index);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800264 if (!page)/* it was truncated */
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700265 continue;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800266 if (IS_ERR(page)) {/* or EIO */
Harvey Harrison9746077a72008-04-28 02:16:17 -0700267 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800268 "read of page %llu failed\n",
269 (unsigned long long)index);
270 continue;
271 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700272 } else
273 page = locked_page;
274
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700275 head = page_buffers(page);
276 bh = head;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800277 pos = i & mask;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800278 for (j = 0; j < pos; ++j)
279 bh = bh->b_this_page;
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800280
281
282 if (unlikely(index == last_index))
283 lblock = end & mask;
284 else
285 lblock = blks_per_page;
286
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700287 do {
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800288 if (j >= lblock)
289 break;
290 pos = (i - beg) + j;
291
292 if (!buffer_mapped(bh))
293 map_bh(bh, inode->i_sb, oldb + pos);
294 if (!buffer_uptodate(bh)) {
295 ll_rw_block(READ, 1, &bh);
296 wait_on_buffer(bh);
297 if (!buffer_uptodate(bh)) {
Harvey Harrison9746077a72008-04-28 02:16:17 -0700298 ufs_error(inode->i_sb, __func__,
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800299 "read of block failed\n");
300 break;
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800301 }
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700302 }
303
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800304 UFSD(" change from %llu to %llu, pos %u\n",
Andrew Morton9df13032008-03-19 17:01:05 -0700305 (unsigned long long)(pos + oldb),
306 (unsigned long long)(pos + newb), pos);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800307
308 bh->b_blocknr = newb + pos;
309 unmap_underlying_metadata(bh->b_bdev,
310 bh->b_blocknr);
311 mark_buffer_dirty(bh);
312 ++j;
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700313 bh = bh->b_this_page;
314 } while (bh != head);
315
Evgeniy Dushistov10e5dce2006-07-01 04:36:24 -0700316 if (likely(cur_index != index))
317 ufs_put_locked_page(page);
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700318 }
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700319 UFSD("EXIT\n");
Evgeniy Dushistov6ef4d6b2006-06-25 05:47:20 -0700320}
321
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800322static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
323 int sync)
324{
325 struct buffer_head *bh;
326 sector_t end = beg + n;
327
328 for (; beg < end; ++beg) {
329 bh = sb_getblk(inode->i_sb, beg);
330 lock_buffer(bh);
331 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
332 set_buffer_uptodate(bh);
333 mark_buffer_dirty(bh);
334 unlock_buffer(bh);
335 if (IS_SYNC(inode) || sync)
336 sync_dirty_buffer(bh);
337 brelse(bh);
338 }
339}
340
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800341u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
342 u64 goal, unsigned count, int *err,
343 struct page *locked_page)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344{
345 struct super_block * sb;
346 struct ufs_sb_private_info * uspi;
347 struct ufs_super_block_first * usb1;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800348 unsigned cgno, oldcount, newcount;
349 u64 tmp, request, result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800351 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
352 inode->i_ino, (unsigned long long)fragment,
353 (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354
355 sb = inode->i_sb;
356 uspi = UFS_SB(sb)->s_uspi;
Evgeniy7b4ee732006-01-14 11:42:06 +0300357 usb1 = ubh_get_usb_first(uspi);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358 *err = -ENOSPC;
359
Fabian Frederick02447562014-06-06 14:38:34 -0700360 lock_ufs(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800361 tmp = ufs_data_ptr_to_cpu(sb, p);
362
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800364 ufs_warning(sb, "ufs_new_fragments", "internal warning"
365 " fragment %llu, count %u",
366 (unsigned long long)fragment, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700367 count = uspi->s_fpb - ufs_fragnum(fragment);
368 }
369 oldcount = ufs_fragnum (fragment);
370 newcount = oldcount + count;
371
372 /*
373 * Somebody else has just allocated our fragments
374 */
375 if (oldcount) {
376 if (!tmp) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800377 ufs_error(sb, "ufs_new_fragments", "internal error, "
378 "fragment %llu, tmp %llu\n",
379 (unsigned long long)fragment,
380 (unsigned long long)tmp);
Fabian Frederick02447562014-06-06 14:38:34 -0700381 unlock_ufs(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800382 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383 }
384 if (fragment < UFS_I(inode)->i_lastfrag) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700385 UFSD("EXIT (ALREADY ALLOCATED)\n");
Fabian Frederick02447562014-06-06 14:38:34 -0700386 unlock_ufs(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387 return 0;
388 }
389 }
390 else {
391 if (tmp) {
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700392 UFSD("EXIT (ALREADY ALLOCATED)\n");
Fabian Frederick02447562014-06-06 14:38:34 -0700393 unlock_ufs(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394 return 0;
395 }
396 }
397
398 /*
399 * There is not enough space for user on the device
400 */
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700401 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
Fabian Frederick02447562014-06-06 14:38:34 -0700402 unlock_ufs(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700403 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404 return 0;
405 }
406
407 if (goal >= uspi->s_size)
408 goal = 0;
409 if (goal == 0)
410 cgno = ufs_inotocg (inode->i_ino);
411 else
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800412 cgno = ufs_dtog(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413
414 /*
415 * allocate new fragment
416 */
417 if (oldcount == 0) {
418 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
419 if (result) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800420 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 *err = 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800422 UFS_I(inode)->i_lastfrag =
Dan Carpenter1d582722011-05-26 16:25:12 -0700423 max(UFS_I(inode)->i_lastfrag, fragment + count);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800424 ufs_clear_frags(inode, result + oldcount,
425 newcount - oldcount, locked_page != NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 }
Fabian Frederick02447562014-06-06 14:38:34 -0700427 unlock_ufs(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800428 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429 return result;
430 }
431
432 /*
433 * resize block
434 */
Fabian Frederick45641c82014-06-06 14:36:33 -0700435 result = ufs_add_fragments(inode, tmp, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436 if (result) {
437 *err = 0;
Dan Carpenter1d582722011-05-26 16:25:12 -0700438 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
439 fragment + count);
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800440 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
441 locked_page != NULL);
Fabian Frederick02447562014-06-06 14:38:34 -0700442 unlock_ufs(sb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800443 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700444 return result;
445 }
446
447 /*
448 * allocate new block and move data
449 */
450 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
451 case UFS_OPTSPACE:
452 request = newcount;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700453 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
454 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455 break;
456 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
457 break;
458 default:
459 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
460
461 case UFS_OPTTIME:
462 request = uspi->s_fpb;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700463 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 (uspi->s_minfree - 2) / 100)
465 break;
466 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
467 break;
468 }
469 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
470 if (result) {
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800471 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
472 locked_page != NULL);
Evgeniy Dushistov4b25a372007-03-16 13:38:09 -0800473 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
474 uspi->s_sbbase + tmp,
475 uspi->s_sbbase + result, locked_page);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800476 ufs_cpu_to_data_ptr(sb, p, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 *err = 0;
Dan Carpenter1d582722011-05-26 16:25:12 -0700478 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
479 fragment + count);
Fabian Frederick02447562014-06-06 14:38:34 -0700480 unlock_ufs(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481 if (newcount < request)
482 ufs_free_fragments (inode, result + newcount, request - newcount);
483 ufs_free_fragments (inode, tmp, oldcount);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800484 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485 return result;
486 }
487
Fabian Frederick02447562014-06-06 14:38:34 -0700488 unlock_ufs(sb);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700489 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490 return 0;
491}
492
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800493static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
Fabian Frederick45641c82014-06-06 14:36:33 -0700494 unsigned oldcount, unsigned newcount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700495{
496 struct super_block * sb;
497 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498 struct ufs_cg_private_info * ucpi;
499 struct ufs_cylinder_group * ucg;
500 unsigned cgno, fragno, fragoff, count, fragsize, i;
501
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800502 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
503 (unsigned long long)fragment, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504
505 sb = inode->i_sb;
506 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700507 count = newcount - oldcount;
508
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800509 cgno = ufs_dtog(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
511 return 0;
512 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
513 return 0;
514 ucpi = ufs_load_cylinder (sb, cgno);
515 if (!ucpi)
516 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700517 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518 if (!ufs_cg_chkmagic(sb, ucg)) {
519 ufs_panic (sb, "ufs_add_fragments",
520 "internal error, bad magic number on cg %u", cgno);
521 return 0;
522 }
523
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800524 fragno = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525 fragoff = ufs_fragnum (fragno);
526 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700527 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528 return 0;
529 /*
530 * Block can be extended
531 */
532 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
533 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700534 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535 break;
536 fragsize = i - oldcount;
537 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
538 ufs_panic (sb, "ufs_add_fragments",
539 "internal error or corrupted bitmap on cg %u", cgno);
540 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
541 if (fragsize != count)
542 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
543 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700544 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700545
546 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
547 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700548 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700550 ubh_mark_buffer_dirty (USPI_UBH(uspi));
551 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200552 if (sb->s_flags & MS_SYNCHRONOUS)
553 ubh_sync_block(UCPI_UBH(ucpi));
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300554 ufs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800556 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557
558 return fragment;
559}
560
561#define UFS_TEST_FREE_SPACE_CG \
562 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
563 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
564 goto cg_found; \
565 for (k = count; k < uspi->s_fpb; k++) \
566 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
567 goto cg_found;
568
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800569static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
570 u64 goal, unsigned count, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571{
572 struct super_block * sb;
573 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574 struct ufs_cg_private_info * ucpi;
575 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800576 unsigned oldcg, i, j, k, allocsize;
577 u64 result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800579 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
580 inode->i_ino, cgno, (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581
582 sb = inode->i_sb;
583 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584 oldcg = cgno;
585
586 /*
587 * 1. searching on preferred cylinder group
588 */
589 UFS_TEST_FREE_SPACE_CG
590
591 /*
592 * 2. quadratic rehash
593 */
594 for (j = 1; j < uspi->s_ncg; j *= 2) {
595 cgno += j;
596 if (cgno >= uspi->s_ncg)
597 cgno -= uspi->s_ncg;
598 UFS_TEST_FREE_SPACE_CG
599 }
600
601 /*
602 * 3. brute force search
603 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
604 */
605 cgno = (oldcg + 1) % uspi->s_ncg;
606 for (j = 2; j < uspi->s_ncg; j++) {
607 cgno++;
608 if (cgno >= uspi->s_ncg)
609 cgno = 0;
610 UFS_TEST_FREE_SPACE_CG
611 }
612
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700613 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614 return 0;
615
616cg_found:
617 ucpi = ufs_load_cylinder (sb, cgno);
618 if (!ucpi)
619 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700620 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621 if (!ufs_cg_chkmagic(sb, ucg))
622 ufs_panic (sb, "ufs_alloc_fragments",
623 "internal error, bad magic number on cg %u", cgno);
624 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
625
626 if (count == uspi->s_fpb) {
627 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800628 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629 return 0;
630 goto succed;
631 }
632
633 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
634 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
635 break;
636
637 if (allocsize == uspi->s_fpb) {
638 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800639 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640 return 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800641 goal = ufs_dtogd(uspi, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642 for (i = count; i < uspi->s_fpb; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700643 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 i = uspi->s_fpb - count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645
646 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700647 uspi->cs_total.cs_nffree += i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
649 fs32_add(sb, &ucg->cg_frsum[i], 1);
650 goto succed;
651 }
652
653 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800654 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 for (i = 0; i < count; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700657 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658
659 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700660 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
662 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
663
664 if (count != allocsize)
665 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
666
667succed:
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700668 ubh_mark_buffer_dirty (USPI_UBH(uspi));
669 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200670 if (sb->s_flags & MS_SYNCHRONOUS)
671 ubh_sync_block(UCPI_UBH(ucpi));
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300672 ufs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673
674 result += cgno * uspi->s_fpg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800675 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676 return result;
677}
678
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800679static u64 ufs_alloccg_block(struct inode *inode,
680 struct ufs_cg_private_info *ucpi,
681 u64 goal, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682{
683 struct super_block * sb;
684 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800686 u64 result, blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700687
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800688 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689
690 sb = inode->i_sb;
691 uspi = UFS_SB(sb)->s_uspi;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700692 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700693
694 if (goal == 0) {
695 goal = ucpi->c_rotor;
696 goto norot;
697 }
698 goal = ufs_blknum (goal);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800699 goal = ufs_dtogd(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700
701 /*
702 * If the requested block is available, use it.
703 */
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700704 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 result = goal;
706 goto gotit;
707 }
708
709norot:
710 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800711 if (result == INVBLOCK)
712 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 ucpi->c_rotor = result;
714gotit:
715 blkno = ufs_fragstoblks(result);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700716 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
718 ufs_clusteracct (sb, ucpi, blkno, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700719
720 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700721 uspi->cs_total.cs_nbfree--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700722 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800723
724 if (uspi->fs_magic != UFS2_MAGIC) {
725 unsigned cylno = ufs_cbtocylno((unsigned)result);
726
727 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
728 ufs_cbtorpos((unsigned)result)), 1);
729 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
730 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800732 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700733
734 return result;
735}
736
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700737static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
738 struct ufs_buffer_head *ubh,
739 unsigned begin, unsigned size,
740 unsigned char *table, unsigned char mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741{
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700742 unsigned rest, offset;
743 unsigned char *cp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700746 offset = begin & ~uspi->s_fmask;
747 begin >>= uspi->s_fshift;
748 for (;;) {
749 if ((offset + size) < uspi->s_fsize)
750 rest = size;
751 else
752 rest = uspi->s_fsize - offset;
753 size -= rest;
754 cp = ubh->bh[begin]->b_data + offset;
755 while ((table[*cp++] & mask) == 0 && --rest)
756 ;
757 if (rest || !size)
758 break;
759 begin++;
760 offset = 0;
761 }
762 return (size + rest);
763}
764
765/*
766 * Find a block of the specified size in the specified cylinder group.
767 * @sp: pointer to super block
768 * @ucpi: pointer to cylinder group info
769 * @goal: near which block we want find new one
770 * @count: specified size
771 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800772static u64 ufs_bitmap_search(struct super_block *sb,
773 struct ufs_cg_private_info *ucpi,
774 u64 goal, unsigned count)
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700775{
776 /*
777 * Bit patterns for identifying fragments in the block map
778 * used as ((map & mask_arr) == want_arr)
779 */
780 static const int mask_arr[9] = {
781 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
782 };
783 static const int want_arr[9] = {
784 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
785 };
786 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800787 unsigned start, length, loc;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700788 unsigned pos, want, blockmap, mask, end;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800789 u64 result;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700790
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800791 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
792 (unsigned long long)goal, count);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700793
Linus Torvalds1da177e2005-04-16 15:20:36 -0700794 if (goal)
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800795 start = ufs_dtogd(uspi, goal) >> 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796 else
797 start = ucpi->c_frotor >> 3;
798
799 length = ((uspi->s_fpg + 7) >> 3) - start;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700800 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
802 1 << (count - 1 + (uspi->s_fpb & 7)));
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700803 if (loc == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804 length = start + 1;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700805 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
806 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
807 ufs_fragtable_other,
808 1 << (count - 1 + (uspi->s_fpb & 7)));
809 if (loc == 0) {
810 ufs_error(sb, "ufs_bitmap_search",
811 "bitmap corrupted on cg %u, start %u,"
812 " length %u, count %u, freeoff %u\n",
813 ucpi->c_cgx, start, length, count,
814 ucpi->c_freeoff);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800815 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700816 }
817 start = 0;
818 }
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700819 result = (start + length - loc) << 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820 ucpi->c_frotor = result;
821
822 /*
823 * found the byte in the map
824 */
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700825
826 for (end = result + 8; result < end; result += uspi->s_fpb) {
827 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
828 blockmap <<= 1;
829 mask = mask_arr[count];
830 want = want_arr[count];
831 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
832 if ((blockmap & mask) == want) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800833 UFSD("EXIT, result %llu\n",
834 (unsigned long long)result);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700835 return result + pos;
836 }
837 mask <<= 1;
838 want <<= 1;
839 }
840 }
841
842 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
843 ucpi->c_cgx);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700844 UFSD("EXIT (FAILED)\n");
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800845 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846}
847
848static void ufs_clusteracct(struct super_block * sb,
849 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
850{
851 struct ufs_sb_private_info * uspi;
852 int i, start, end, forw, back;
853
854 uspi = UFS_SB(sb)->s_uspi;
855 if (uspi->s_contigsumsize <= 0)
856 return;
857
858 if (cnt > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700859 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860 else
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700861 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862
863 /*
864 * Find the size of the cluster going forward.
865 */
866 start = blkno + 1;
867 end = start + uspi->s_contigsumsize;
868 if ( end >= ucpi->c_nclusterblks)
869 end = ucpi->c_nclusterblks;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700870 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 if (i > end)
872 i = end;
873 forw = i - start;
874
875 /*
876 * Find the size of the cluster going backward.
877 */
878 start = blkno - 1;
879 end = start - uspi->s_contigsumsize;
880 if (end < 0 )
881 end = -1;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700882 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700883 if ( i < end)
884 i = end;
885 back = start - i;
886
887 /*
888 * Account for old cluster and the possibly new forward and
889 * back clusters.
890 */
891 i = back + forw + 1;
892 if (i > uspi->s_contigsumsize)
893 i = uspi->s_contigsumsize;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700894 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895 if (back > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700896 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897 if (forw > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700898 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899}
900
901
902static unsigned char ufs_fragtable_8fpb[] = {
903 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
904 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
905 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
906 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
907 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
908 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
909 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
910 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
911 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
912 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
913 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
914 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
915 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
916 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
917 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
918 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
919};
920
921static unsigned char ufs_fragtable_other[] = {
922 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
923 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
924 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
925 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
926 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
927 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
928 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
929 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
930 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
931 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
932 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
933 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
934 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
935 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
936 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
937 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
938};