balloc.c 28 KB

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