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