?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
allow coexistance of N build and AC build.
[tomato.git] / release / src-rt-6.x / linux / linux-2.6 / fs / ufs / balloc.c
blob841ac25fd95042f86d134330a13dafd8521521dd
1 /*
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
7 *
8 * UFS2 write support Evgeniy Dushistov <dushistov@mail.ru>, 2007
9 */
10
11 #include <linux/fs.h>
12 #include <linux/ufs_fs.h>
13 #include <linux/stat.h>
14 #include <linux/time.h>
15 #include <linux/string.h>
16 #include <linux/quotaops.h>
17 #include <linux/buffer_head.h>
18 #include <linux/capability.h>
19 #include <linux/bitops.h>
20 #include <asm/byteorder.h>
21
22 #include "swab.h"
23 #include "util.h"
24
25 #define INVBLOCK ((u64)-1L)
26
27 static u64 ufs_add_fragments(struct inode *, u64, unsigned, unsigned, int *);
28 static u64 ufs_alloc_fragments(struct inode *, unsigned, u64, unsigned, int *);
29 static u64 ufs_alloccg_block(struct inode *, struct ufs_cg_private_info *, u64, int *);
30 static u64 ufs_bitmap_search (struct super_block *, struct ufs_cg_private_info *, u64, unsigned);
31 static unsigned char ufs_fragtable_8fpb[], ufs_fragtable_other[];
32 static void ufs_clusteracct(struct super_block *, struct ufs_cg_private_info *, unsigned, int);
33
34 /*
35 * Free 'count' fragments from fragment number 'fragment'
36 */
37 void ufs_free_fragments(struct inode *inode, u64 fragment, unsigned count)
38 {
39 struct super_block * sb;
40 struct ufs_sb_private_info * uspi;
41 struct ufs_super_block_first * usb1;
42 struct ufs_cg_private_info * ucpi;
43 struct ufs_cylinder_group * ucg;
44 unsigned cgno, bit, end_bit, bbase, blkmap, i;
45 u64 blkno;
46
47 sb = inode->i_sb;
48 uspi = UFS_SB(sb)->s_uspi;
49 usb1 = ubh_get_usb_first(uspi);
50
51 UFSD("ENTER, fragment %llu, count %u\n",
52 (unsigned long long)fragment, count);
53
54 if (ufs_fragnum(fragment) + count > uspi->s_fpg)
55 ufs_error (sb, "ufs_free_fragments", "internal error");
56
57 lock_super(sb);
58
59 cgno = ufs_dtog(uspi, fragment);
60 bit = ufs_dtogd(uspi, fragment);
61 if (cgno >= uspi->s_ncg) {
62 ufs_panic (sb, "ufs_free_fragments", "freeing blocks are outside device");
63 goto failed;
64 }
65
66 ucpi = ufs_load_cylinder (sb, cgno);
67 if (!ucpi)
68 goto failed;
69 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
70 if (!ufs_cg_chkmagic(sb, ucg)) {
71 ufs_panic (sb, "ufs_free_fragments", "internal error, bad magic number on cg %u", cgno);
72 goto failed;
73 }
74
75 end_bit = bit + count;
76 bbase = ufs_blknum (bit);
77 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
78 ufs_fragacct (sb, blkmap, ucg->cg_frsum, -1);
79 for (i = bit; i < end_bit; i++) {
80 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, i))
81 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, i);
82 else
83 ufs_error (sb, "ufs_free_fragments",
84 "bit already cleared for fragment %u", i);
85 }
86
87 DQUOT_FREE_BLOCK (inode, count);
88
89
90 fs32_add(sb, &ucg->cg_cs.cs_nffree, count);
91 uspi->cs_total.cs_nffree += count;
92 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
93 blkmap = ubh_blkmap (UCPI_UBH(ucpi), ucpi->c_freeoff, bbase);
94 ufs_fragacct(sb, blkmap, ucg->cg_frsum, 1);
95
96 /*
97 * Trying to reassemble free fragments into block
98 */
99 blkno = ufs_fragstoblks (bbase);
100 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
101 fs32_sub(sb, &ucg->cg_cs.cs_nffree, uspi->s_fpb);
102 uspi->cs_total.cs_nffree -= uspi->s_fpb;
103 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, uspi->s_fpb);
104 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
105 ufs_clusteracct (sb, ucpi, blkno, 1);
106 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
107 uspi->cs_total.cs_nbfree++;
108 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
109 if (uspi->fs_magic != UFS2_MAGIC) {
110 unsigned cylno = ufs_cbtocylno (bbase);
111
112 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
113 ufs_cbtorpos(bbase)), 1);
114 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
115 }
116 }
117
118 ubh_mark_buffer_dirty (USPI_UBH(uspi));
119 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
120 if (sb->s_flags & MS_SYNCHRONOUS) {
121 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
122 ubh_wait_on_buffer (UCPI_UBH(ucpi));
123 }
124 sb->s_dirt = 1;
125
126 unlock_super (sb);
127 UFSD("EXIT\n");
128 return;
129
130 failed:
131 unlock_super (sb);
132 UFSD("EXIT (FAILED)\n");
133 return;
134 }
135
136 /*
137 * Free 'count' fragments from fragment number 'fragment' (free whole blocks)
138 */
139 void ufs_free_blocks(struct inode *inode, u64 fragment, unsigned count)
140 {
141 struct super_block * sb;
142 struct ufs_sb_private_info * uspi;
143 struct ufs_super_block_first * usb1;
144 struct ufs_cg_private_info * ucpi;
145 struct ufs_cylinder_group * ucg;
146 unsigned overflow, cgno, bit, end_bit, i;
147 u64 blkno;
148
149 sb = inode->i_sb;
150 uspi = UFS_SB(sb)->s_uspi;
151 usb1 = ubh_get_usb_first(uspi);
152
153 UFSD("ENTER, fragment %llu, count %u\n",
154 (unsigned long long)fragment, count);
155
156 if ((fragment & uspi->s_fpbmask) || (count & uspi->s_fpbmask)) {
157 ufs_error (sb, "ufs_free_blocks", "internal error, "
158 "fragment %llu, count %u\n",
159 (unsigned long long)fragment, count);
160 goto failed;
161 }
162
163 lock_super(sb);
164
165 do_more:
166 overflow = 0;
167 cgno = ufs_dtog(uspi, fragment);
168 bit = ufs_dtogd(uspi, fragment);
169 if (cgno >= uspi->s_ncg) {
170 ufs_panic (sb, "ufs_free_blocks", "freeing blocks are outside device");
171 goto failed_unlock;
172 }
173 end_bit = bit + count;
174 if (end_bit > uspi->s_fpg) {
175 overflow = bit + count - uspi->s_fpg;
176 count -= overflow;
177 end_bit -= overflow;
178 }
179
180 ucpi = ufs_load_cylinder (sb, cgno);
181 if (!ucpi)
182 goto failed_unlock;
183 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
184 if (!ufs_cg_chkmagic(sb, ucg)) {
185 ufs_panic (sb, "ufs_free_blocks", "internal error, bad magic number on cg %u", cgno);
186 goto failed_unlock;
187 }
188
189 for (i = bit; i < end_bit; i += uspi->s_fpb) {
190 blkno = ufs_fragstoblks(i);
191 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno)) {
192 ufs_error(sb, "ufs_free_blocks", "freeing free fragment");
193 }
194 ubh_setblock(UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
195 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
196 ufs_clusteracct (sb, ucpi, blkno, 1);
197 DQUOT_FREE_BLOCK(inode, uspi->s_fpb);
198
199 fs32_add(sb, &ucg->cg_cs.cs_nbfree, 1);
200 uspi->cs_total.cs_nbfree++;
201 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nbfree, 1);
202
203 if (uspi->fs_magic != UFS2_MAGIC) {
204 unsigned cylno = ufs_cbtocylno(i);
205
206 fs16_add(sb, &ubh_cg_blks(ucpi, cylno,
207 ufs_cbtorpos(i)), 1);
208 fs32_add(sb, &ubh_cg_blktot(ucpi, cylno), 1);
209 }
210 }
211
212 ubh_mark_buffer_dirty (USPI_UBH(uspi));
213 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
214 if (sb->s_flags & MS_SYNCHRONOUS) {
215 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
216 ubh_wait_on_buffer (UCPI_UBH(ucpi));
217 }
218
219 if (overflow) {
220 fragment += count;
221 count = overflow;
222 goto do_more;
223 }
224
225 sb->s_dirt = 1;
226 unlock_super (sb);
227 UFSD("EXIT\n");
228 return;
229
230 failed_unlock:
231 unlock_super (sb);
232 failed:
233 UFSD("EXIT (FAILED)\n");
234 return;
235 }
236
237 /*
238 * Modify inode page cache in such way:
239 * have - blocks with b_blocknr equal to oldb...oldb+count-1
240 * get - blocks with b_blocknr equal to newb...newb+count-1
241 * also we suppose that oldb...oldb+count-1 blocks
242 * situated at the end of file.
243 *
244 * We can come here from ufs_writepage or ufs_prepare_write,
245 * locked_page is argument of these functions, so we already lock it.
246 */
247 static void ufs_change_blocknr(struct inode *inode, sector_t beg,
248 unsigned int count, sector_t oldb,
249 sector_t newb, struct page *locked_page)
250 {
251 const unsigned blks_per_page =
252 1 << (PAGE_CACHE_SHIFT - inode->i_blkbits);
253 const unsigned mask = blks_per_page - 1;
254 struct address_space * const mapping = inode->i_mapping;
255 pgoff_t index, cur_index, last_index;
256 unsigned pos, j, lblock;
257 sector_t end, i;
258 struct page *page;
259 struct buffer_head *head, *bh;
260
261 UFSD("ENTER, ino %lu, count %u, oldb %llu, newb %llu\n",
262 inode->i_ino, count,
263 (unsigned long long)oldb, (unsigned long long)newb);
264
265 BUG_ON(!locked_page);
266 BUG_ON(!PageLocked(locked_page));
267
268 cur_index = locked_page->index;
269 end = count + beg;
270 last_index = end >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
271 for (i = beg; i < end; i = (i | mask) + 1) {
272 index = i >> (PAGE_CACHE_SHIFT - inode->i_blkbits);
273
274 if (likely(cur_index != index)) {
275 page = ufs_get_locked_page(mapping, index);
276 if (!page)/* it was truncated */
277 continue;
278 if (IS_ERR(page)) {/* or EIO */
279 ufs_error(inode->i_sb, __FUNCTION__,
280 "read of page %llu failed\n",
281 (unsigned long long)index);
282 continue;
283 }
284 } else
285 page = locked_page;
286
287 head = page_buffers(page);
288 bh = head;
289 pos = i & mask;
290 for (j = 0; j < pos; ++j)
291 bh = bh->b_this_page;
292
293
294 if (unlikely(index == last_index))
295 lblock = end & mask;
296 else
297 lblock = blks_per_page;
298
299 do {
300 if (j >= lblock)
301 break;
302 pos = (i - beg) + j;
303
304 if (!buffer_mapped(bh))
305 map_bh(bh, inode->i_sb, oldb + pos);
306 if (!buffer_uptodate(bh)) {
307 ll_rw_block(READ, 1, &bh);
308 wait_on_buffer(bh);
309 if (!buffer_uptodate(bh)) {
310 ufs_error(inode->i_sb, __FUNCTION__,
311 "read of block failed\n");
312 break;
313 }
314 }
315
316 UFSD(" change from %llu to %llu, pos %u\n",
317 (unsigned long long)pos + oldb,
318 (unsigned long long)pos + newb, pos);
319
320 bh->b_blocknr = newb + pos;
321 unmap_underlying_metadata(bh->b_bdev,
322 bh->b_blocknr);
323 mark_buffer_dirty(bh);
324 ++j;
325 bh = bh->b_this_page;
326 } while (bh != head);
327
328 if (likely(cur_index != index))
329 ufs_put_locked_page(page);
330 }
331 UFSD("EXIT\n");
332 }
333
334 static void ufs_clear_frags(struct inode *inode, sector_t beg, unsigned int n,
335 int sync)
336 {
337 struct buffer_head *bh;
338 sector_t end = beg + n;
339
340 for (; beg < end; ++beg) {
341 bh = sb_getblk(inode->i_sb, beg);
342 lock_buffer(bh);
343 memset(bh->b_data, 0, inode->i_sb->s_blocksize);
344 set_buffer_uptodate(bh);
345 mark_buffer_dirty(bh);
346 unlock_buffer(bh);
347 if (IS_SYNC(inode) || sync)
348 sync_dirty_buffer(bh);
349 brelse(bh);
350 }
351 }
352
353 u64 ufs_new_fragments(struct inode *inode, void *p, u64 fragment,
354 u64 goal, unsigned count, int *err,
355 struct page *locked_page)
356 {
357 struct super_block * sb;
358 struct ufs_sb_private_info * uspi;
359 struct ufs_super_block_first * usb1;
360 unsigned cgno, oldcount, newcount;
361 u64 tmp, request, result;
362
363 UFSD("ENTER, ino %lu, fragment %llu, goal %llu, count %u\n",
364 inode->i_ino, (unsigned long long)fragment,
365 (unsigned long long)goal, count);
366
367 sb = inode->i_sb;
368 uspi = UFS_SB(sb)->s_uspi;
369 usb1 = ubh_get_usb_first(uspi);
370 *err = -ENOSPC;
371
372 lock_super (sb);
373 tmp = ufs_data_ptr_to_cpu(sb, p);
374
375 if (count + ufs_fragnum(fragment) > uspi->s_fpb) {
376 ufs_warning(sb, "ufs_new_fragments", "internal warning"
377 " fragment %llu, count %u",
378 (unsigned long long)fragment, count);
379 count = uspi->s_fpb - ufs_fragnum(fragment);
380 }
381 oldcount = ufs_fragnum (fragment);
382 newcount = oldcount + count;
383
384 /*
385 * Somebody else has just allocated our fragments
386 */
387 if (oldcount) {
388 if (!tmp) {
389 ufs_error(sb, "ufs_new_fragments", "internal error, "
390 "fragment %llu, tmp %llu\n",
391 (unsigned long long)fragment,
392 (unsigned long long)tmp);
393 unlock_super(sb);
394 return INVBLOCK;
395 }
396 if (fragment < UFS_I(inode)->i_lastfrag) {
397 UFSD("EXIT (ALREADY ALLOCATED)\n");
398 unlock_super (sb);
399 return 0;
400 }
401 }
402 else {
403 if (tmp) {
404 UFSD("EXIT (ALREADY ALLOCATED)\n");
405 unlock_super(sb);
406 return 0;
407 }
408 }
409
410 /*
411 * There is not enough space for user on the device
412 */
413 if (!capable(CAP_SYS_RESOURCE) && ufs_freespace(uspi, UFS_MINFREE) <= 0) {
414 unlock_super (sb);
415 UFSD("EXIT (FAILED)\n");
416 return 0;
417 }
418
419 if (goal >= uspi->s_size)
420 goal = 0;
421 if (goal == 0)
422 cgno = ufs_inotocg (inode->i_ino);
423 else
424 cgno = ufs_dtog(uspi, goal);
425
426 /*
427 * allocate new fragment
428 */
429 if (oldcount == 0) {
430 result = ufs_alloc_fragments (inode, cgno, goal, count, err);
431 if (result) {
432 ufs_cpu_to_data_ptr(sb, p, result);
433 *err = 0;
434 UFS_I(inode)->i_lastfrag =
435 max_t(u32, UFS_I(inode)->i_lastfrag,
436 fragment + count);
437 ufs_clear_frags(inode, result + oldcount,
438 newcount - oldcount, locked_page != NULL);
439 }
440 unlock_super(sb);
441 UFSD("EXIT, result %llu\n", (unsigned long long)result);
442 return result;
443 }
444
445 /*
446 * resize block
447 */
448 result = ufs_add_fragments (inode, tmp, oldcount, newcount, err);
449 if (result) {
450 *err = 0;
451 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
452 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
453 locked_page != NULL);
454 unlock_super(sb);
455 UFSD("EXIT, result %llu\n", (unsigned long long)result);
456 return result;
457 }
458
459 /*
460 * allocate new block and move data
461 */
462 switch (fs32_to_cpu(sb, usb1->fs_optim)) {
463 case UFS_OPTSPACE:
464 request = newcount;
465 if (uspi->s_minfree < 5 || uspi->cs_total.cs_nffree
466 > uspi->s_dsize * uspi->s_minfree / (2 * 100))
467 break;
468 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
469 break;
470 default:
471 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
472
473 case UFS_OPTTIME:
474 request = uspi->s_fpb;
475 if (uspi->cs_total.cs_nffree < uspi->s_dsize *
476 (uspi->s_minfree - 2) / 100)
477 break;
478 usb1->fs_optim = cpu_to_fs32(sb, UFS_OPTTIME);
479 break;
480 }
481 result = ufs_alloc_fragments (inode, cgno, goal, request, err);
482 if (result) {
483 ufs_clear_frags(inode, result + oldcount, newcount - oldcount,
484 locked_page != NULL);
485 ufs_change_blocknr(inode, fragment - oldcount, oldcount,
486 uspi->s_sbbase + tmp,
487 uspi->s_sbbase + result, locked_page);
488 ufs_cpu_to_data_ptr(sb, p, result);
489 *err = 0;
490 UFS_I(inode)->i_lastfrag = max_t(u32, UFS_I(inode)->i_lastfrag, fragment + count);
491 unlock_super(sb);
492 if (newcount < request)
493 ufs_free_fragments (inode, result + newcount, request - newcount);
494 ufs_free_fragments (inode, tmp, oldcount);
495 UFSD("EXIT, result %llu\n", (unsigned long long)result);
496 return result;
497 }
498
499 unlock_super(sb);
500 UFSD("EXIT (FAILED)\n");
501 return 0;
502 }
503
504 static u64 ufs_add_fragments(struct inode *inode, u64 fragment,
505 unsigned oldcount, unsigned newcount, int *err)
506 {
507 struct super_block * sb;
508 struct ufs_sb_private_info * uspi;
509 struct ufs_super_block_first * usb1;
510 struct ufs_cg_private_info * ucpi;
511 struct ufs_cylinder_group * ucg;
512 unsigned cgno, fragno, fragoff, count, fragsize, i;
513
514 UFSD("ENTER, fragment %llu, oldcount %u, newcount %u\n",
515 (unsigned long long)fragment, oldcount, newcount);
516
517 sb = inode->i_sb;
518 uspi = UFS_SB(sb)->s_uspi;
519 usb1 = ubh_get_usb_first (uspi);
520 count = newcount - oldcount;
521
522 cgno = ufs_dtog(uspi, fragment);
523 if (fs32_to_cpu(sb, UFS_SB(sb)->fs_cs(cgno).cs_nffree) < count)
524 return 0;
525 if ((ufs_fragnum (fragment) + newcount) > uspi->s_fpb)
526 return 0;
527 ucpi = ufs_load_cylinder (sb, cgno);
528 if (!ucpi)
529 return 0;
530 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
531 if (!ufs_cg_chkmagic(sb, ucg)) {
532 ufs_panic (sb, "ufs_add_fragments",
533 "internal error, bad magic number on cg %u", cgno);
534 return 0;
535 }
536
537 fragno = ufs_dtogd(uspi, fragment);
538 fragoff = ufs_fragnum (fragno);
539 for (i = oldcount; i < newcount; i++)
540 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
541 return 0;
542 /*
543 * Block can be extended
544 */
545 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
546 for (i = newcount; i < (uspi->s_fpb - fragoff); i++)
547 if (ubh_isclr (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i))
548 break;
549 fragsize = i - oldcount;
550 if (!fs32_to_cpu(sb, ucg->cg_frsum[fragsize]))
551 ufs_panic (sb, "ufs_add_fragments",
552 "internal error or corrupted bitmap on cg %u", cgno);
553 fs32_sub(sb, &ucg->cg_frsum[fragsize], 1);
554 if (fragsize != count)
555 fs32_add(sb, &ucg->cg_frsum[fragsize - count], 1);
556 for (i = oldcount; i < newcount; i++)
557 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, fragno + i);
558 if(DQUOT_ALLOC_BLOCK(inode, count)) {
559 *err = -EDQUOT;
560 return 0;
561 }
562
563 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
564 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
565 uspi->cs_total.cs_nffree -= count;
566
567 ubh_mark_buffer_dirty (USPI_UBH(uspi));
568 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
569 if (sb->s_flags & MS_SYNCHRONOUS) {
570 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
571 ubh_wait_on_buffer (UCPI_UBH(ucpi));
572 }
573 sb->s_dirt = 1;
574
575 UFSD("EXIT, fragment %llu\n", (unsigned long long)fragment);
576
577 return fragment;
578 }
579
580 #define UFS_TEST_FREE_SPACE_CG \
581 ucg = (struct ufs_cylinder_group *) UFS_SB(sb)->s_ucg[cgno]->b_data; \
582 if (fs32_to_cpu(sb, ucg->cg_cs.cs_nbfree)) \
583 goto cg_found; \
584 for (k = count; k < uspi->s_fpb; k++) \
585 if (fs32_to_cpu(sb, ucg->cg_frsum[k])) \
586 goto cg_found;
587
588 static u64 ufs_alloc_fragments(struct inode *inode, unsigned cgno,
589 u64 goal, unsigned count, int *err)
590 {
591 struct super_block * sb;
592 struct ufs_sb_private_info * uspi;
593 struct ufs_super_block_first * usb1;
594 struct ufs_cg_private_info * ucpi;
595 struct ufs_cylinder_group * ucg;
596 unsigned oldcg, i, j, k, allocsize;
597 u64 result;
598
599 UFSD("ENTER, ino %lu, cgno %u, goal %llu, count %u\n",
600 inode->i_ino, cgno, (unsigned long long)goal, count);
601
602 sb = inode->i_sb;
603 uspi = UFS_SB(sb)->s_uspi;
604 usb1 = ubh_get_usb_first(uspi);
605 oldcg = cgno;
606
607 /*
608 * 1. searching on preferred cylinder group
609 */
610 UFS_TEST_FREE_SPACE_CG
611
612 /*
613 * 2. quadratic rehash
614 */
615 for (j = 1; j < uspi->s_ncg; j *= 2) {
616 cgno += j;
617 if (cgno >= uspi->s_ncg)
618 cgno -= uspi->s_ncg;
619 UFS_TEST_FREE_SPACE_CG
620 }
621
622 /*
623 * 3. brute force search
624 * We start at i = 2 ( 0 is checked at 1.step, 1 at 2.step )
625 */
626 cgno = (oldcg + 1) % uspi->s_ncg;
627 for (j = 2; j < uspi->s_ncg; j++) {
628 cgno++;
629 if (cgno >= uspi->s_ncg)
630 cgno = 0;
631 UFS_TEST_FREE_SPACE_CG
632 }
633
634 UFSD("EXIT (FAILED)\n");
635 return 0;
636
637 cg_found:
638 ucpi = ufs_load_cylinder (sb, cgno);
639 if (!ucpi)
640 return 0;
641 ucg = ubh_get_ucg (UCPI_UBH(ucpi));
642 if (!ufs_cg_chkmagic(sb, ucg))
643 ufs_panic (sb, "ufs_alloc_fragments",
644 "internal error, bad magic number on cg %u", cgno);
645 ucg->cg_time = cpu_to_fs32(sb, get_seconds());
646
647 if (count == uspi->s_fpb) {
648 result = ufs_alloccg_block (inode, ucpi, goal, err);
649 if (result == INVBLOCK)
650 return 0;
651 goto succed;
652 }
653
654 for (allocsize = count; allocsize < uspi->s_fpb; allocsize++)
655 if (fs32_to_cpu(sb, ucg->cg_frsum[allocsize]) != 0)
656 break;
657
658 if (allocsize == uspi->s_fpb) {
659 result = ufs_alloccg_block (inode, ucpi, goal, err);
660 if (result == INVBLOCK)
661 return 0;
662 goal = ufs_dtogd(uspi, result);
663 for (i = count; i < uspi->s_fpb; i++)
664 ubh_setbit (UCPI_UBH(ucpi), ucpi->c_freeoff, goal + i);
665 i = uspi->s_fpb - count;
666 DQUOT_FREE_BLOCK(inode, i);
667
668 fs32_add(sb, &ucg->cg_cs.cs_nffree, i);
669 uspi->cs_total.cs_nffree += i;
670 fs32_add(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, i);
671 fs32_add(sb, &ucg->cg_frsum[i], 1);
672 goto succed;
673 }
674
675 result = ufs_bitmap_search (sb, ucpi, goal, allocsize);
676 if (result == INVBLOCK)
677 return 0;
678 if(DQUOT_ALLOC_BLOCK(inode, count)) {
679 *err = -EDQUOT;
680 return 0;
681 }
682 for (i = 0; i < count; i++)
683 ubh_clrbit (UCPI_UBH(ucpi), ucpi->c_freeoff, result + i);
684
685 fs32_sub(sb, &ucg->cg_cs.cs_nffree, count);
686 uspi->cs_total.cs_nffree -= count;
687 fs32_sub(sb, &UFS_SB(sb)->fs_cs(cgno).cs_nffree, count);
688 fs32_sub(sb, &ucg->cg_frsum[allocsize], 1);
689
690 if (count != allocsize)
691 fs32_add(sb, &ucg->cg_frsum[allocsize - count], 1);
692
693 succed:
694 ubh_mark_buffer_dirty (USPI_UBH(uspi));
695 ubh_mark_buffer_dirty (UCPI_UBH(ucpi));
696 if (sb->s_flags & MS_SYNCHRONOUS) {
697 ubh_ll_rw_block(SWRITE, UCPI_UBH(ucpi));
698 ubh_wait_on_buffer (UCPI_UBH(ucpi));
699 }
700 sb->s_dirt = 1;
701
702 result += cgno * uspi->s_fpg;
703 UFSD("EXIT3, result %llu\n", (unsigned long long)result);
704 return result;
705 }
706
707 static u64 ufs_alloccg_block(struct inode *inode,
708 struct ufs_cg_private_info *ucpi,
709 u64 goal, int *err)
710 {
711 struct super_block * sb;
712 struct ufs_sb_private_info * uspi;
713 struct ufs_super_block_first * usb1;
714 struct ufs_cylinder_group * ucg;
715 u64 result, blkno;
716
717 UFSD("ENTER, goal %llu\n", (unsigned long long)goal);
718
719 sb = inode->i_sb;
720 uspi = UFS_SB(sb)->s_uspi;
721 usb1 = ubh_get_usb_first(uspi);
722 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
723
724 if (goal == 0) {
725 goal = ucpi->c_rotor;
726 goto norot;
727 }
728 goal = ufs_blknum (goal);
729 goal = ufs_dtogd(uspi, goal);
730
731 /*
732 * If the requested block is available, use it.
733 */
734 if (ubh_isblockset(UCPI_UBH(ucpi), ucpi->c_freeoff, ufs_fragstoblks(goal))) {
735 result = goal;
736 goto gotit;
737 }
738
739 norot:
740 result = ufs_bitmap_search (sb, ucpi, goal, uspi->s_fpb);
741 if (result == INVBLOCK)
742 return INVBLOCK;
743 ucpi->c_rotor = result;
744 gotit:
745 blkno = ufs_fragstoblks(result);
746 ubh_clrblock (UCPI_UBH(ucpi), ucpi->c_freeoff, blkno);
747 if ((UFS_SB(sb)->s_flags & UFS_CG_MASK) == UFS_CG_44BSD)
748 ufs_clusteracct (sb, ucpi, blkno, -1);
749 if(DQUOT_ALLOC_BLOCK(inode, uspi->s_fpb)) {
750 *err = -EDQUOT;
751 return INVBLOCK;
752 }
753
754 fs32_sub(sb, &ucg->cg_cs.cs_nbfree, 1);
755 uspi->cs_total.cs_nbfree--;
756 fs32_sub(sb, &UFS_SB(sb)->fs_cs(ucpi->c_cgx).cs_nbfree, 1);
757
758 if (uspi->fs_magic != UFS2_MAGIC) {
759 unsigned cylno = ufs_cbtocylno((unsigned)result);
760
761 fs16_sub(sb, &ubh_cg_blks(ucpi, cylno,
762 ufs_cbtorpos((unsigned)result)), 1);
763 fs32_sub(sb, &ubh_cg_blktot(ucpi, cylno), 1);
764 }
765
766 UFSD("EXIT, result %llu\n", (unsigned long long)result);
767
768 return result;
769 }
770
771 static unsigned ubh_scanc(struct ufs_sb_private_info *uspi,
772 struct ufs_buffer_head *ubh,
773 unsigned begin, unsigned size,
774 unsigned char *table, unsigned char mask)
775 {
776 unsigned rest, offset;
777 unsigned char *cp;
778
779
780 offset = begin & ~uspi->s_fmask;
781 begin >>= uspi->s_fshift;
782 for (;;) {
783 if ((offset + size) < uspi->s_fsize)
784 rest = size;
785 else
786 rest = uspi->s_fsize - offset;
787 size -= rest;
788 cp = ubh->bh[begin]->b_data + offset;
789 while ((table[*cp++] & mask) == 0 && --rest)
790 ;
791 if (rest || !size)
792 break;
793 begin++;
794 offset = 0;
795 }
796 return (size + rest);
797 }
798
799 /*
800 * Find a block of the specified size in the specified cylinder group.
801 * @sp: pointer to super block
802 * @ucpi: pointer to cylinder group info
803 * @goal: near which block we want find new one
804 * @count: specified size
805 */
806 static u64 ufs_bitmap_search(struct super_block *sb,
807 struct ufs_cg_private_info *ucpi,
808 u64 goal, unsigned count)
809 {
810 /*
811 * Bit patterns for identifying fragments in the block map
812 * used as ((map & mask_arr) == want_arr)
813 */
814 static const int mask_arr[9] = {
815 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff
816 };
817 static const int want_arr[9] = {
818 0x0, 0x2, 0x6, 0xe, 0x1e, 0x3e, 0x7e, 0xfe, 0x1fe
819 };
820 struct ufs_sb_private_info *uspi = UFS_SB(sb)->s_uspi;
821 struct ufs_super_block_first *usb1;
822 struct ufs_cylinder_group *ucg;
823 unsigned start, length, loc;
824 unsigned pos, want, blockmap, mask, end;
825 u64 result;
826
827 UFSD("ENTER, cg %u, goal %llu, count %u\n", ucpi->c_cgx,
828 (unsigned long long)goal, count);
829
830 usb1 = ubh_get_usb_first (uspi);
831 ucg = ubh_get_ucg(UCPI_UBH(ucpi));
832
833 if (goal)
834 start = ufs_dtogd(uspi, goal) >> 3;
835 else
836 start = ucpi->c_frotor >> 3;
837
838 length = ((uspi->s_fpg + 7) >> 3) - start;
839 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff + start, length,
840 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb : ufs_fragtable_other,
841 1 << (count - 1 + (uspi->s_fpb & 7)));
842 if (loc == 0) {
843 length = start + 1;
844 loc = ubh_scanc(uspi, UCPI_UBH(ucpi), ucpi->c_freeoff, length,
845 (uspi->s_fpb == 8) ? ufs_fragtable_8fpb :
846 ufs_fragtable_other,
847 1 << (count - 1 + (uspi->s_fpb & 7)));
848 if (loc == 0) {
849 ufs_error(sb, "ufs_bitmap_search",
850 "bitmap corrupted on cg %u, start %u,"
851 " length %u, count %u, freeoff %u\n",
852 ucpi->c_cgx, start, length, count,
853 ucpi->c_freeoff);
854 return INVBLOCK;
855 }
856 start = 0;
857 }
858 result = (start + length - loc) << 3;
859 ucpi->c_frotor = result;
860
861 /*
862 * found the byte in the map
863 */
864
865 for (end = result + 8; result < end; result += uspi->s_fpb) {
866 blockmap = ubh_blkmap(UCPI_UBH(ucpi), ucpi->c_freeoff, result);
867 blockmap <<= 1;
868 mask = mask_arr[count];
869 want = want_arr[count];
870 for (pos = 0; pos <= uspi->s_fpb - count; pos++) {
871 if ((blockmap & mask) == want) {
872 UFSD("EXIT, result %llu\n",
873 (unsigned long long)result);
874 return result + pos;
875 }
876 mask <<= 1;
877 want <<= 1;
878 }
879 }
880
881 ufs_error(sb, "ufs_bitmap_search", "block not in map on cg %u\n",
882 ucpi->c_cgx);
883 UFSD("EXIT (FAILED)\n");
884 return INVBLOCK;
885 }
886
887 static void ufs_clusteracct(struct super_block * sb,
888 struct ufs_cg_private_info * ucpi, unsigned blkno, int cnt)
889 {
890 struct ufs_sb_private_info * uspi;
891 int i, start, end, forw, back;
892
893 uspi = UFS_SB(sb)->s_uspi;
894 if (uspi->s_contigsumsize <= 0)
895 return;
896
897 if (cnt > 0)
898 ubh_setbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
899 else
900 ubh_clrbit(UCPI_UBH(ucpi), ucpi->c_clusteroff, blkno);
901
902 /*
903 * Find the size of the cluster going forward.
904 */
905 start = blkno + 1;
906 end = start + uspi->s_contigsumsize;
907 if ( end >= ucpi->c_nclusterblks)
908 end = ucpi->c_nclusterblks;
909 i = ubh_find_next_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, end, start);
910 if (i > end)
911 i = end;
912 forw = i - start;
913
914 /*
915 * Find the size of the cluster going backward.
916 */
917 start = blkno - 1;
918 end = start - uspi->s_contigsumsize;
919 if (end < 0 )
920 end = -1;
921 i = ubh_find_last_zero_bit (UCPI_UBH(ucpi), ucpi->c_clusteroff, start, end);
922 if ( i < end)
923 i = end;
924 back = start - i;
925
926 /*
927 * Account for old cluster and the possibly new forward and
928 * back clusters.
929 */
930 i = back + forw + 1;
931 if (i > uspi->s_contigsumsize)
932 i = uspi->s_contigsumsize;
933 fs32_add(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (i << 2)), cnt);
934 if (back > 0)
935 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (back << 2)), cnt);
936 if (forw > 0)
937 fs32_sub(sb, (__fs32*)ubh_get_addr(UCPI_UBH(ucpi), ucpi->c_clustersumoff + (forw << 2)), cnt);
938 }
939
940
941 static unsigned char ufs_fragtable_8fpb[] = {
942 0x00, 0x01, 0x01, 0x02, 0x01, 0x01, 0x02, 0x04, 0x01, 0x01, 0x01, 0x03, 0x02, 0x03, 0x04, 0x08,
943 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x02, 0x03, 0x03, 0x02, 0x04, 0x05, 0x08, 0x10,
944 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
945 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x04, 0x05, 0x05, 0x06, 0x08, 0x09, 0x10, 0x20,
946 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
947 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
948 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
949 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x08, 0x09, 0x09, 0x0A, 0x10, 0x11, 0x20, 0x40,
950 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
951 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x03, 0x03, 0x03, 0x03, 0x05, 0x05, 0x09, 0x11,
952 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x03, 0x05, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x05, 0x09,
953 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x05, 0x05, 0x05, 0x07, 0x09, 0x09, 0x11, 0x21,
954 0x02, 0x03, 0x03, 0x02, 0x03, 0x03, 0x02, 0x06, 0x03, 0x03, 0x03, 0x03, 0x02, 0x03, 0x06, 0x0A,
955 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x07, 0x02, 0x03, 0x03, 0x02, 0x06, 0x07, 0x0A, 0x12,
956 0x04, 0x05, 0x05, 0x06, 0x05, 0x05, 0x06, 0x04, 0x05, 0x05, 0x05, 0x07, 0x06, 0x07, 0x04, 0x0C,
957 0x08, 0x09, 0x09, 0x0A, 0x09, 0x09, 0x0A, 0x0C, 0x10, 0x11, 0x11, 0x12, 0x20, 0x21, 0x40, 0x80,
958 };
959
960 static unsigned char ufs_fragtable_other[] = {
961 0x00, 0x16, 0x16, 0x2A, 0x16, 0x16, 0x26, 0x4E, 0x16, 0x16, 0x16, 0x3E, 0x2A, 0x3E, 0x4E, 0x8A,
962 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
963 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
964 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
965 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
966 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
967 0x26, 0x36, 0x36, 0x2E, 0x36, 0x36, 0x26, 0x6E, 0x36, 0x36, 0x36, 0x3E, 0x2E, 0x3E, 0x6E, 0xAE,
968 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
969 0x16, 0x16, 0x16, 0x3E, 0x16, 0x16, 0x36, 0x5E, 0x16, 0x16, 0x16, 0x3E, 0x3E, 0x3E, 0x5E, 0x9E,
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 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
973 0x2A, 0x3E, 0x3E, 0x2A, 0x3E, 0x3E, 0x2E, 0x6E, 0x3E, 0x3E, 0x3E, 0x3E, 0x2A, 0x3E, 0x6E, 0xAA,
974 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x3E, 0x7E, 0xBE,
975 0x4E, 0x5E, 0x5E, 0x6E, 0x5E, 0x5E, 0x6E, 0x4E, 0x5E, 0x5E, 0x5E, 0x7E, 0x6E, 0x7E, 0x4E, 0xCE,
976 0x8A, 0x9E, 0x9E, 0xAA, 0x9E, 0x9E, 0xAE, 0xCE, 0x9E, 0x9E, 0x9E, 0xBE, 0xAA, 0xBE, 0xCE, 0x8A,
977 };
Tomato firmware and modifications.