blob: 67e085d591d8398aaf07ab0102e602b70ca9ae8e [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");
Fabian Frederickcdd9eef2015-06-10 10:09:32 +100054
55 mutex_lock(&UFS_SB(sb)->s_lock);
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);
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000118
119 mutex_unlock(&UFS_SB(sb)->s_lock);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700120 UFSD("EXIT\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 return;
122
123failed:
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000124 mutex_unlock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000154 mutex_lock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000214 mutex_unlock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000219 mutex_unlock(&UFS_SB(sb)->s_lock);
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 =
Kirill A. Shutemov09cbfea2016-04-01 15:29:47 +0300240 1 << (PAGE_SHIFT - inode->i_blkbits);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800241 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;
Kirill A. Shutemov09cbfea2016-04-01 15:29:47 +0300258 last_index = end >> (PAGE_SHIFT - inode->i_blkbits);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800259 for (i = beg; i < end; i = (i | mask) + 1) {
Kirill A. Shutemov09cbfea2016-04-01 15:29:47 +0300260 index = i >> (PAGE_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)) {
Mike Christiedfec8a12016-06-05 14:31:44 -0500295 ll_rw_block(REQ_OP_READ, 0, 1, &bh);
Evgeniy Dushistov5431bf92007-03-16 13:38:08 -0800296 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 Frederickcdd9eef2015-06-10 10:09:32 +1000360 mutex_lock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000381 mutex_unlock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000386 mutex_unlock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000393 mutex_unlock(&UFS_SB(sb)->s_lock);
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 Frederickcdd9eef2015-06-10 10:09:32 +1000402 mutex_unlock(&UFS_SB(sb)->s_lock);
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) {
Al Virobd2843f2015-09-09 10:16:39 +0100420 ufs_clear_frags(inode, result + oldcount,
421 newcount - oldcount, locked_page != NULL);
Al Viro724bb092015-06-17 12:02:56 -0400422 write_seqlock(&UFS_I(inode)->meta_lock);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800423 ufs_cpu_to_data_ptr(sb, p, result);
Al Viro724bb092015-06-17 12:02:56 -0400424 write_sequnlock(&UFS_I(inode)->meta_lock);
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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428 }
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000429 mutex_unlock(&UFS_SB(sb)->s_lock);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800430 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431 return result;
432 }
433
434 /*
435 * resize block
436 */
Fabian Frederick45641c82014-06-06 14:36:33 -0700437 result = ufs_add_fragments(inode, tmp, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 if (result) {
439 *err = 0;
Dan Carpenter1d582722011-05-26 16:25:12 -0700440 UFS_I(inode)->i_lastfrag = max(UFS_I(inode)->i_lastfrag,
441 fragment + count);
Evgeniy Dushistovd63b7092007-01-05 16:37:04 -0800442 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
443 locked_page != NULL);
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000444 mutex_unlock(&UFS_SB(sb)->s_lock);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800445 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446 return result;
447 }
448
449 /*
450 * allocate new block and move data
451 */
452 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
453 case UFS_OPTSPACE:
454 request = newcount;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700455 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
456 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700457 break;
458 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
459 break;
460 default:
461 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
462
463 case UFS_OPTTIME:
464 request = uspi->s_fpb;
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700465 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 (uspi->s_minfree - 2) / 100)
467 break;
468 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
469 break;
470 }
471 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
472 if (result) {
Evgeniy Dushistovefee2b82007-01-29 13:19:56 -0800473 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
474 locked_page != NULL);
Evgeniy Dushistov4b25a372007-03-16 13:38:09 -0800475 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
476 uspi->s_sbbase + tmp,
477 uspi->s_sbbase + result, locked_page);
Al Viro724bb092015-06-17 12:02:56 -0400478 write_seqlock(&UFS_I(inode)->meta_lock);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800479 ufs_cpu_to_data_ptr(sb, p, result);
Al Viro724bb092015-06-17 12:02:56 -0400480 write_sequnlock(&UFS_I(inode)->meta_lock);
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);
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000484 mutex_unlock(&UFS_SB(sb)->s_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485 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
Fabian Frederickcdd9eef2015-06-10 10:09:32 +1000492 mutex_unlock(&UFS_SB(sb)->s_lock);
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,
Fabian Frederick45641c82014-06-06 14:36:33 -0700498 unsigned oldcount, unsigned newcount)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700499{
500 struct super_block * sb;
501 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 struct ufs_cg_private_info * ucpi;
503 struct ufs_cylinder_group * ucg;
504 unsigned cgno, fragno, fragoff, count, fragsize, i;
505
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800506 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
507 (unsigned long long)fragment, oldcount, newcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508
509 sb = inode->i_sb;
510 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 count = newcount - oldcount;
512
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800513 cgno = ufs_dtog(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700514 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
515 return 0;
516 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
517 return 0;
518 ucpi = ufs_load_cylinder (sb, cgno);
519 if (!ucpi)
520 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700521 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700522 if (!ufs_cg_chkmagic(sb, ucg)) {
523 ufs_panic (sb, "ufs_add_fragments",
524 "internal error, bad magic number on cg %u", cgno);
525 return 0;
526 }
527
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800528 fragno = ufs_dtogd(uspi, fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529 fragoff = ufs_fragnum (fragno);
530 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700531 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 return 0;
533 /*
534 * Block can be extended
535 */
536 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
537 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700538 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700539 break;
540 fragsize = i - oldcount;
541 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
542 ufs_panic (sb, "ufs_add_fragments",
543 "internal error or corrupted bitmap on cg %u", cgno);
544 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
545 if (fragsize != count)
546 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
547 for (i = oldcount; i < newcount; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700548 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549
550 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
551 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700552 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700554 ubh_mark_buffer_dirty (USPI_UBH(uspi));
555 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200556 if (sb->s_flags & MS_SYNCHRONOUS)
557 ubh_sync_block(UCPI_UBH(ucpi));
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300558 ufs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800560 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561
562 return fragment;
563}
564
565#define UFS_TEST_FREE_SPACE_CG \
566 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
567 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
568 goto cg_found; \
569 for (k = count; k < uspi->s_fpb; k++) \
570 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
571 goto cg_found;
572
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800573static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
574 u64 goal, unsigned count, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575{
576 struct super_block * sb;
577 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578 struct ufs_cg_private_info * ucpi;
579 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800580 unsigned oldcg, i, j, k, allocsize;
581 u64 result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800583 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
584 inode->i_ino, cgno, (unsigned long long)goal, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585
586 sb = inode->i_sb;
587 uspi = UFS_SB(sb)->s_uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700588 oldcg = cgno;
589
590 /*
591 * 1. searching on preferred cylinder group
592 */
593 UFS_TEST_FREE_SPACE_CG
594
595 /*
596 * 2. quadratic rehash
597 */
598 for (j = 1; j < uspi->s_ncg; j *= 2) {
599 cgno += j;
600 if (cgno >= uspi->s_ncg)
601 cgno -= uspi->s_ncg;
602 UFS_TEST_FREE_SPACE_CG
603 }
604
605 /*
606 * 3. brute force search
607 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
608 */
609 cgno = (oldcg + 1) % uspi->s_ncg;
610 for (j = 2; j < uspi->s_ncg; j++) {
611 cgno++;
612 if (cgno >= uspi->s_ncg)
613 cgno = 0;
614 UFS_TEST_FREE_SPACE_CG
615 }
616
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700617 UFSD("EXIT (FAILED)\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700618 return 0;
619
620cg_found:
621 ucpi = ufs_load_cylinder (sb, cgno);
622 if (!ucpi)
623 return 0;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700624 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625 if (!ufs_cg_chkmagic(sb, ucg))
626 ufs_panic (sb, "ufs_alloc_fragments",
627 "internal error, bad magic number on cg %u", cgno);
628 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
629
630 if (count == uspi->s_fpb) {
631 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800632 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633 return 0;
634 goto succed;
635 }
636
637 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
638 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
639 break;
640
641 if (allocsize == uspi->s_fpb) {
642 result = ufs_alloccg_block (inode, ucpi, goal, err);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800643 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 return 0;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800645 goal = ufs_dtogd(uspi, result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646 for (i = count; i < uspi->s_fpb; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700647 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 i = uspi->s_fpb - count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649
650 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700651 uspi->cs_total.cs_nffree += i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
653 fs32_add(sb, &ucg->cg_frsum[i], 1);
654 goto succed;
655 }
656
657 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800658 if (result == INVBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700660 for (i = 0; i < count; i++)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700661 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662
663 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700664 uspi->cs_total.cs_nffree -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
666 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
667
668 if (count != allocsize)
669 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
670
671succed:
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700672 ubh_mark_buffer_dirty (USPI_UBH(uspi));
673 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
Christoph Hellwig9cb569d2010-08-11 17:06:24 +0200674 if (sb->s_flags & MS_SYNCHRONOUS)
675 ubh_sync_block(UCPI_UBH(ucpi));
Artem Bityutskiy9e9ad5f2012-07-12 16:28:08 +0300676 ufs_mark_sb_dirty(sb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677
678 result += cgno * uspi->s_fpg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800679 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 return result;
681}
682
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800683static u64 ufs_alloccg_block(struct inode *inode,
684 struct ufs_cg_private_info *ucpi,
685 u64 goal, int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700686{
687 struct super_block * sb;
688 struct ufs_sb_private_info * uspi;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689 struct ufs_cylinder_group * ucg;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800690 u64 result, blkno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800692 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700693
694 sb = inode->i_sb;
695 uspi = UFS_SB(sb)->s_uspi;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700696 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697
698 if (goal == 0) {
699 goal = ucpi->c_rotor;
700 goto norot;
701 }
702 goal = ufs_blknum (goal);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800703 goal = ufs_dtogd(uspi, goal);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700704
705 /*
706 * If the requested block is available, use it.
707 */
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700708 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700709 result = goal;
710 goto gotit;
711 }
712
713norot:
714 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800715 if (result == INVBLOCK)
716 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700717 ucpi->c_rotor = result;
718gotit:
719 blkno = ufs_fragstoblks(result);
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700720 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
722 ufs_clusteracct (sb, ucpi, blkno, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700723
724 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
Evgeniy Dushistovee3ffd62006-06-25 05:47:30 -0700725 uspi->cs_total.cs_nbfree--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800727
728 if (uspi->fs_magic != UFS2_MAGIC) {
729 unsigned cylno = ufs_cbtocylno((unsigned)result);
730
731 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
732 ufs_cbtorpos((unsigned)result)), 1);
733 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
734 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800736 UFSD("EXIT, result %llu\n", (unsigned long long)result);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700737
738 return result;
739}
740
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700741static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
742 struct ufs_buffer_head *ubh,
743 unsigned begin, unsigned size,
744 unsigned char *table, unsigned char mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745{
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700746 unsigned rest, offset;
747 unsigned char *cp;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700748
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700750 offset = begin & ~uspi->s_fmask;
751 begin >>= uspi->s_fshift;
752 for (;;) {
753 if ((offset + size) < uspi->s_fsize)
754 rest = size;
755 else
756 rest = uspi->s_fsize - offset;
757 size -= rest;
758 cp = ubh->bh[begin]->b_data + offset;
759 while ((table[*cp++] & mask) == 0 && --rest)
760 ;
761 if (rest || !size)
762 break;
763 begin++;
764 offset = 0;
765 }
766 return (size + rest);
767}
768
769/*
770 * Find a block of the specified size in the specified cylinder group.
771 * @sp: pointer to super block
772 * @ucpi: pointer to cylinder group info
773 * @goal: near which block we want find new one
774 * @count: specified size
775 */
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800776static u64 ufs_bitmap_search(struct super_block *sb,
777 struct ufs_cg_private_info *ucpi,
778 u64 goal, unsigned count)
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700779{
780 /*
781 * Bit patterns for identifying fragments in the block map
782 * used as ((map & mask_arr) == want_arr)
783 */
784 static const int mask_arr[9] = {
785 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
786 };
787 static const int want_arr[9] = {
788 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
789 };
790 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800791 unsigned start, length, loc;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700792 unsigned pos, want, blockmap, mask, end;
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800793 u64 result;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700794
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800795 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
796 (unsigned long long)goal, count);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700797
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798 if (goal)
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800799 start = ufs_dtogd(uspi, goal) >> 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700800 else
801 start = ucpi->c_frotor >> 3;
802
803 length = ((uspi->s_fpg + 7) >> 3) - start;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700804 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700805 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
806 1 << (count - 1 + (uspi->s_fpb & 7)));
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700807 if (loc == 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700808 length = start + 1;
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700809 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
810 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
811 ufs_fragtable_other,
812 1 << (count - 1 + (uspi->s_fpb & 7)));
813 if (loc == 0) {
814 ufs_error(sb, "ufs_bitmap_search",
815 "bitmap corrupted on cg %u, start %u,"
816 " length %u, count %u, freeoff %u\n",
817 ucpi->c_cgx, start, length, count,
818 ucpi->c_freeoff);
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800819 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820 }
821 start = 0;
822 }
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700823 result = (start + length - loc) << 3;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824 ucpi->c_frotor = result;
825
826 /*
827 * found the byte in the map
828 */
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700829
830 for (end = result + 8; result < end; result += uspi->s_fpb) {
831 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
832 blockmap <<= 1;
833 mask = mask_arr[count];
834 want = want_arr[count];
835 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
836 if ((blockmap & mask) == want) {
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800837 UFSD("EXIT, result %llu\n",
838 (unsigned long long)result);
Evgeniy Dushistov3e41f592006-06-25 05:47:23 -0700839 return result + pos;
840 }
841 mask <<= 1;
842 want <<= 1;
843 }
844 }
845
846 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
847 ucpi->c_cgx);
Evgeniy Dushistovabf5d152006-06-25 05:47:24 -0700848 UFSD("EXIT (FAILED)\n");
Evgeniy Dushistov54fb9962007-02-12 00:54:32 -0800849 return INVBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850}
851
852static void ufs_clusteracct(struct super_block * sb,
853 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
854{
855 struct ufs_sb_private_info * uspi;
856 int i, start, end, forw, back;
857
858 uspi = UFS_SB(sb)->s_uspi;
859 if (uspi->s_contigsumsize <= 0)
860 return;
861
862 if (cnt > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700863 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700864 else
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700865 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866
867 /*
868 * Find the size of the cluster going forward.
869 */
870 start = blkno + 1;
871 end = start + uspi->s_contigsumsize;
872 if ( end >= ucpi->c_nclusterblks)
873 end = ucpi->c_nclusterblks;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700874 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 if (i > end)
876 i = end;
877 forw = i - start;
878
879 /*
880 * Find the size of the cluster going backward.
881 */
882 start = blkno - 1;
883 end = start - uspi->s_contigsumsize;
884 if (end < 0 )
885 end = -1;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700886 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700887 if ( i < end)
888 i = end;
889 back = start - i;
890
891 /*
892 * Account for old cluster and the possibly new forward and
893 * back clusters.
894 */
895 i = back + forw + 1;
896 if (i > uspi->s_contigsumsize)
897 i = uspi->s_contigsumsize;
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700898 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899 if (back > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700900 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700901 if (forw > 0)
Evgeniy Dushistov9695ef12006-06-25 05:47:22 -0700902 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903}
904
905
906static unsigned char ufs_fragtable_8fpb[] = {
907 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
908 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
909 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
910 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
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 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
914 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
915 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
916 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
917 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
918 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
919 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
920 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
921 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
922 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
923};
924
925static unsigned char ufs_fragtable_other[] = {
926 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
927 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
928 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
929 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
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 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
933 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
934 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
935 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
936 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
937 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
938 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
939 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
940 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
941 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
942};