alloc.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * alloc.c - NILFS dat/inode allocator
  4. *
  5. * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
  6. *
  7. * Originally written by Koji Sato.
  8. * Two allocators were unified by Ryusuke Konishi and Amagai Yoshiji.
  9. */
  10. #include <linux/types.h>
  11. #include <linux/buffer_head.h>
  12. #include <linux/fs.h>
  13. #include <linux/bitops.h>
  14. #include <linux/slab.h>
  15. #include "mdt.h"
  16. #include "alloc.h"
  17. /**
  18. * nilfs_palloc_groups_per_desc_block - get the number of groups that a group
  19. * descriptor block can maintain
  20. * @inode: inode of metadata file using this allocator
  21. */
  22. static inline unsigned long
  23. nilfs_palloc_groups_per_desc_block(const struct inode *inode)
  24. {
  25. return i_blocksize(inode) /
  26. sizeof(struct nilfs_palloc_group_desc);
  27. }
  28. /**
  29. * nilfs_palloc_groups_count - get maximum number of groups
  30. * @inode: inode of metadata file using this allocator
  31. */
  32. static inline unsigned long
  33. nilfs_palloc_groups_count(const struct inode *inode)
  34. {
  35. return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
  36. }
  37. /**
  38. * nilfs_palloc_init_blockgroup - initialize private variables for allocator
  39. * @inode: inode of metadata file using this allocator
  40. * @entry_size: size of the persistent object
  41. */
  42. int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned int entry_size)
  43. {
  44. struct nilfs_mdt_info *mi = NILFS_MDT(inode);
  45. mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS);
  46. if (!mi->mi_bgl)
  47. return -ENOMEM;
  48. bgl_lock_init(mi->mi_bgl);
  49. nilfs_mdt_set_entry_size(inode, entry_size, 0);
  50. mi->mi_blocks_per_group =
  51. DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode),
  52. mi->mi_entries_per_block) + 1;
  53. /*
  54. * Number of blocks in a group including entry blocks
  55. * and a bitmap block
  56. */
  57. mi->mi_blocks_per_desc_block =
  58. nilfs_palloc_groups_per_desc_block(inode) *
  59. mi->mi_blocks_per_group + 1;
  60. /*
  61. * Number of blocks per descriptor including the
  62. * descriptor block
  63. */
  64. return 0;
  65. }
  66. /**
  67. * nilfs_palloc_group - get group number and offset from an entry number
  68. * @inode: inode of metadata file using this allocator
  69. * @nr: serial number of the entry (e.g. inode number)
  70. * @offset: pointer to store offset number in the group
  71. */
  72. static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr,
  73. unsigned long *offset)
  74. {
  75. __u64 group = nr;
  76. *offset = do_div(group, nilfs_palloc_entries_per_group(inode));
  77. return group;
  78. }
  79. /**
  80. * nilfs_palloc_desc_blkoff - get block offset of a group descriptor block
  81. * @inode: inode of metadata file using this allocator
  82. * @group: group number
  83. *
  84. * nilfs_palloc_desc_blkoff() returns block offset of the descriptor
  85. * block which contains a descriptor of the specified group.
  86. */
  87. static unsigned long
  88. nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group)
  89. {
  90. unsigned long desc_block =
  91. group / nilfs_palloc_groups_per_desc_block(inode);
  92. return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block;
  93. }
  94. /**
  95. * nilfs_palloc_bitmap_blkoff - get block offset of a bitmap block
  96. * @inode: inode of metadata file using this allocator
  97. * @group: group number
  98. *
  99. * nilfs_palloc_bitmap_blkoff() returns block offset of the bitmap
  100. * block used to allocate/deallocate entries in the specified group.
  101. */
  102. static unsigned long
  103. nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group)
  104. {
  105. unsigned long desc_offset =
  106. group % nilfs_palloc_groups_per_desc_block(inode);
  107. return nilfs_palloc_desc_blkoff(inode, group) + 1 +
  108. desc_offset * NILFS_MDT(inode)->mi_blocks_per_group;
  109. }
  110. /**
  111. * nilfs_palloc_group_desc_nfrees - get the number of free entries in a group
  112. * @desc: pointer to descriptor structure for the group
  113. * @lock: spin lock protecting @desc
  114. */
  115. static unsigned long
  116. nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc *desc,
  117. spinlock_t *lock)
  118. {
  119. unsigned long nfree;
  120. spin_lock(lock);
  121. nfree = le32_to_cpu(desc->pg_nfrees);
  122. spin_unlock(lock);
  123. return nfree;
  124. }
  125. /**
  126. * nilfs_palloc_group_desc_add_entries - adjust count of free entries
  127. * @desc: pointer to descriptor structure for the group
  128. * @lock: spin lock protecting @desc
  129. * @n: delta to be added
  130. */
  131. static u32
  132. nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc *desc,
  133. spinlock_t *lock, u32 n)
  134. {
  135. u32 nfree;
  136. spin_lock(lock);
  137. le32_add_cpu(&desc->pg_nfrees, n);
  138. nfree = le32_to_cpu(desc->pg_nfrees);
  139. spin_unlock(lock);
  140. return nfree;
  141. }
  142. /**
  143. * nilfs_palloc_entry_blkoff - get block offset of an entry block
  144. * @inode: inode of metadata file using this allocator
  145. * @nr: serial number of the entry (e.g. inode number)
  146. */
  147. static unsigned long
  148. nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr)
  149. {
  150. unsigned long group, group_offset;
  151. group = nilfs_palloc_group(inode, nr, &group_offset);
  152. return nilfs_palloc_bitmap_blkoff(inode, group) + 1 +
  153. group_offset / NILFS_MDT(inode)->mi_entries_per_block;
  154. }
  155. /**
  156. * nilfs_palloc_desc_block_init - initialize buffer of a group descriptor block
  157. * @inode: inode of metadata file
  158. * @bh: buffer head of the buffer to be initialized
  159. * @kaddr: kernel address mapped for the page including the buffer
  160. */
  161. static void nilfs_palloc_desc_block_init(struct inode *inode,
  162. struct buffer_head *bh, void *kaddr)
  163. {
  164. struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh);
  165. unsigned long n = nilfs_palloc_groups_per_desc_block(inode);
  166. __le32 nfrees;
  167. nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode));
  168. while (n-- > 0) {
  169. desc->pg_nfrees = nfrees;
  170. desc++;
  171. }
  172. }
  173. static int nilfs_palloc_get_block(struct inode *inode, unsigned long blkoff,
  174. int create,
  175. void (*init_block)(struct inode *,
  176. struct buffer_head *,
  177. void *),
  178. struct buffer_head **bhp,
  179. struct nilfs_bh_assoc *prev,
  180. spinlock_t *lock)
  181. {
  182. int ret;
  183. spin_lock(lock);
  184. if (prev->bh && blkoff == prev->blkoff) {
  185. get_bh(prev->bh);
  186. *bhp = prev->bh;
  187. spin_unlock(lock);
  188. return 0;
  189. }
  190. spin_unlock(lock);
  191. ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp);
  192. if (!ret) {
  193. spin_lock(lock);
  194. /*
  195. * The following code must be safe for change of the
  196. * cache contents during the get block call.
  197. */
  198. brelse(prev->bh);
  199. get_bh(*bhp);
  200. prev->bh = *bhp;
  201. prev->blkoff = blkoff;
  202. spin_unlock(lock);
  203. }
  204. return ret;
  205. }
  206. /**
  207. * nilfs_palloc_delete_block - delete a block on the persistent allocator file
  208. * @inode: inode of metadata file using this allocator
  209. * @blkoff: block offset
  210. * @prev: nilfs_bh_assoc struct of the last used buffer
  211. * @lock: spin lock protecting @prev
  212. */
  213. static int nilfs_palloc_delete_block(struct inode *inode, unsigned long blkoff,
  214. struct nilfs_bh_assoc *prev,
  215. spinlock_t *lock)
  216. {
  217. spin_lock(lock);
  218. if (prev->bh && blkoff == prev->blkoff) {
  219. brelse(prev->bh);
  220. prev->bh = NULL;
  221. }
  222. spin_unlock(lock);
  223. return nilfs_mdt_delete_block(inode, blkoff);
  224. }
  225. /**
  226. * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block
  227. * @inode: inode of metadata file using this allocator
  228. * @group: group number
  229. * @create: create flag
  230. * @bhp: pointer to store the resultant buffer head
  231. */
  232. static int nilfs_palloc_get_desc_block(struct inode *inode,
  233. unsigned long group,
  234. int create, struct buffer_head **bhp)
  235. {
  236. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  237. return nilfs_palloc_get_block(inode,
  238. nilfs_palloc_desc_blkoff(inode, group),
  239. create, nilfs_palloc_desc_block_init,
  240. bhp, &cache->prev_desc, &cache->lock);
  241. }
  242. /**
  243. * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block
  244. * @inode: inode of metadata file using this allocator
  245. * @group: group number
  246. * @create: create flag
  247. * @bhp: pointer to store the resultant buffer head
  248. */
  249. static int nilfs_palloc_get_bitmap_block(struct inode *inode,
  250. unsigned long group,
  251. int create, struct buffer_head **bhp)
  252. {
  253. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  254. return nilfs_palloc_get_block(inode,
  255. nilfs_palloc_bitmap_blkoff(inode, group),
  256. create, NULL, bhp,
  257. &cache->prev_bitmap, &cache->lock);
  258. }
  259. /**
  260. * nilfs_palloc_delete_bitmap_block - delete a bitmap block
  261. * @inode: inode of metadata file using this allocator
  262. * @group: group number
  263. */
  264. static int nilfs_palloc_delete_bitmap_block(struct inode *inode,
  265. unsigned long group)
  266. {
  267. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  268. return nilfs_palloc_delete_block(inode,
  269. nilfs_palloc_bitmap_blkoff(inode,
  270. group),
  271. &cache->prev_bitmap, &cache->lock);
  272. }
  273. /**
  274. * nilfs_palloc_get_entry_block - get buffer head of an entry block
  275. * @inode: inode of metadata file using this allocator
  276. * @nr: serial number of the entry (e.g. inode number)
  277. * @create: create flag
  278. * @bhp: pointer to store the resultant buffer head
  279. */
  280. int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
  281. int create, struct buffer_head **bhp)
  282. {
  283. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  284. return nilfs_palloc_get_block(inode,
  285. nilfs_palloc_entry_blkoff(inode, nr),
  286. create, NULL, bhp,
  287. &cache->prev_entry, &cache->lock);
  288. }
  289. /**
  290. * nilfs_palloc_delete_entry_block - delete an entry block
  291. * @inode: inode of metadata file using this allocator
  292. * @nr: serial number of the entry
  293. */
  294. static int nilfs_palloc_delete_entry_block(struct inode *inode, __u64 nr)
  295. {
  296. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  297. return nilfs_palloc_delete_block(inode,
  298. nilfs_palloc_entry_blkoff(inode, nr),
  299. &cache->prev_entry, &cache->lock);
  300. }
  301. /**
  302. * nilfs_palloc_block_get_group_desc - get kernel address of a group descriptor
  303. * @inode: inode of metadata file using this allocator
  304. * @group: group number
  305. * @bh: buffer head of the buffer storing the group descriptor block
  306. * @kaddr: kernel address mapped for the page including the buffer
  307. */
  308. static struct nilfs_palloc_group_desc *
  309. nilfs_palloc_block_get_group_desc(const struct inode *inode,
  310. unsigned long group,
  311. const struct buffer_head *bh, void *kaddr)
  312. {
  313. return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
  314. group % nilfs_palloc_groups_per_desc_block(inode);
  315. }
  316. /**
  317. * nilfs_palloc_block_get_entry - get kernel address of an entry
  318. * @inode: inode of metadata file using this allocator
  319. * @nr: serial number of the entry (e.g. inode number)
  320. * @bh: buffer head of the buffer storing the entry block
  321. * @kaddr: kernel address mapped for the page including the buffer
  322. */
  323. void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
  324. const struct buffer_head *bh, void *kaddr)
  325. {
  326. unsigned long entry_offset, group_offset;
  327. nilfs_palloc_group(inode, nr, &group_offset);
  328. entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
  329. return kaddr + bh_offset(bh) +
  330. entry_offset * NILFS_MDT(inode)->mi_entry_size;
  331. }
  332. /**
  333. * nilfs_palloc_find_available_slot - find available slot in a group
  334. * @bitmap: bitmap of the group
  335. * @target: offset number of an entry in the group (start point)
  336. * @bsize: size in bits
  337. * @lock: spin lock protecting @bitmap
  338. */
  339. static int nilfs_palloc_find_available_slot(unsigned char *bitmap,
  340. unsigned long target,
  341. unsigned int bsize,
  342. spinlock_t *lock)
  343. {
  344. int pos, end = bsize;
  345. if (likely(target < bsize)) {
  346. pos = target;
  347. do {
  348. pos = nilfs_find_next_zero_bit(bitmap, end, pos);
  349. if (pos >= end)
  350. break;
  351. if (!nilfs_set_bit_atomic(lock, pos, bitmap))
  352. return pos;
  353. } while (++pos < end);
  354. end = target;
  355. }
  356. /* wrap around */
  357. for (pos = 0; pos < end; pos++) {
  358. pos = nilfs_find_next_zero_bit(bitmap, end, pos);
  359. if (pos >= end)
  360. break;
  361. if (!nilfs_set_bit_atomic(lock, pos, bitmap))
  362. return pos;
  363. }
  364. return -ENOSPC;
  365. }
  366. /**
  367. * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups
  368. * in a group descriptor block
  369. * @inode: inode of metadata file using this allocator
  370. * @curr: current group number
  371. * @max: maximum number of groups
  372. */
  373. static unsigned long
  374. nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
  375. unsigned long curr, unsigned long max)
  376. {
  377. return min_t(unsigned long,
  378. nilfs_palloc_groups_per_desc_block(inode) -
  379. curr % nilfs_palloc_groups_per_desc_block(inode),
  380. max - curr + 1);
  381. }
  382. /**
  383. * nilfs_palloc_count_desc_blocks - count descriptor blocks number
  384. * @inode: inode of metadata file using this allocator
  385. * @desc_blocks: descriptor blocks number [out]
  386. */
  387. static int nilfs_palloc_count_desc_blocks(struct inode *inode,
  388. unsigned long *desc_blocks)
  389. {
  390. __u64 blknum;
  391. int ret;
  392. ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum);
  393. if (likely(!ret))
  394. *desc_blocks = DIV_ROUND_UP(
  395. (unsigned long)blknum,
  396. NILFS_MDT(inode)->mi_blocks_per_desc_block);
  397. return ret;
  398. }
  399. /**
  400. * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
  401. * MDT file growing
  402. * @inode: inode of metadata file using this allocator
  403. * @desc_blocks: known current descriptor blocks count
  404. */
  405. static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
  406. unsigned long desc_blocks)
  407. {
  408. return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) <
  409. nilfs_palloc_groups_count(inode);
  410. }
  411. /**
  412. * nilfs_palloc_count_max_entries - count max number of entries that can be
  413. * described by descriptor blocks count
  414. * @inode: inode of metadata file using this allocator
  415. * @nused: current number of used entries
  416. * @nmaxp: max number of entries [out]
  417. */
  418. int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
  419. {
  420. unsigned long desc_blocks = 0;
  421. u64 entries_per_desc_block, nmax;
  422. int err;
  423. err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks);
  424. if (unlikely(err))
  425. return err;
  426. entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
  427. nilfs_palloc_groups_per_desc_block(inode);
  428. nmax = entries_per_desc_block * desc_blocks;
  429. if (nused == nmax &&
  430. nilfs_palloc_mdt_file_can_grow(inode, desc_blocks))
  431. nmax += entries_per_desc_block;
  432. if (nused > nmax)
  433. return -ERANGE;
  434. *nmaxp = nmax;
  435. return 0;
  436. }
  437. /**
  438. * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
  439. * @inode: inode of metadata file using this allocator
  440. * @req: nilfs_palloc_req structure exchanged for the allocation
  441. */
  442. int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
  443. struct nilfs_palloc_req *req)
  444. {
  445. struct buffer_head *desc_bh, *bitmap_bh;
  446. struct nilfs_palloc_group_desc *desc;
  447. unsigned char *bitmap;
  448. void *desc_kaddr, *bitmap_kaddr;
  449. unsigned long group, maxgroup, ngroups;
  450. unsigned long group_offset, maxgroup_offset;
  451. unsigned long n, entries_per_group;
  452. unsigned long i, j;
  453. spinlock_t *lock;
  454. int pos, ret;
  455. ngroups = nilfs_palloc_groups_count(inode);
  456. maxgroup = ngroups - 1;
  457. group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
  458. entries_per_group = nilfs_palloc_entries_per_group(inode);
  459. for (i = 0; i < ngroups; i += n) {
  460. if (group >= ngroups) {
  461. /* wrap around */
  462. group = 0;
  463. maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
  464. &maxgroup_offset) - 1;
  465. }
  466. ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
  467. if (ret < 0)
  468. return ret;
  469. desc_kaddr = kmap(desc_bh->b_page);
  470. desc = nilfs_palloc_block_get_group_desc(
  471. inode, group, desc_bh, desc_kaddr);
  472. n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
  473. maxgroup);
  474. for (j = 0; j < n; j++, desc++, group++) {
  475. lock = nilfs_mdt_bgl_lock(inode, group);
  476. if (nilfs_palloc_group_desc_nfrees(desc, lock) > 0) {
  477. ret = nilfs_palloc_get_bitmap_block(
  478. inode, group, 1, &bitmap_bh);
  479. if (ret < 0)
  480. goto out_desc;
  481. bitmap_kaddr = kmap(bitmap_bh->b_page);
  482. bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
  483. pos = nilfs_palloc_find_available_slot(
  484. bitmap, group_offset,
  485. entries_per_group, lock);
  486. if (pos >= 0) {
  487. /* found a free entry */
  488. nilfs_palloc_group_desc_add_entries(
  489. desc, lock, -1);
  490. req->pr_entry_nr =
  491. entries_per_group * group + pos;
  492. kunmap(desc_bh->b_page);
  493. kunmap(bitmap_bh->b_page);
  494. req->pr_desc_bh = desc_bh;
  495. req->pr_bitmap_bh = bitmap_bh;
  496. return 0;
  497. }
  498. kunmap(bitmap_bh->b_page);
  499. brelse(bitmap_bh);
  500. }
  501. group_offset = 0;
  502. }
  503. kunmap(desc_bh->b_page);
  504. brelse(desc_bh);
  505. }
  506. /* no entries left */
  507. return -ENOSPC;
  508. out_desc:
  509. kunmap(desc_bh->b_page);
  510. brelse(desc_bh);
  511. return ret;
  512. }
  513. /**
  514. * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
  515. * @inode: inode of metadata file using this allocator
  516. * @req: nilfs_palloc_req structure exchanged for the allocation
  517. */
  518. void nilfs_palloc_commit_alloc_entry(struct inode *inode,
  519. struct nilfs_palloc_req *req)
  520. {
  521. mark_buffer_dirty(req->pr_bitmap_bh);
  522. mark_buffer_dirty(req->pr_desc_bh);
  523. nilfs_mdt_mark_dirty(inode);
  524. brelse(req->pr_bitmap_bh);
  525. brelse(req->pr_desc_bh);
  526. }
  527. /**
  528. * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
  529. * @inode: inode of metadata file using this allocator
  530. * @req: nilfs_palloc_req structure exchanged for the removal
  531. */
  532. void nilfs_palloc_commit_free_entry(struct inode *inode,
  533. struct nilfs_palloc_req *req)
  534. {
  535. struct nilfs_palloc_group_desc *desc;
  536. unsigned long group, group_offset;
  537. unsigned char *bitmap;
  538. void *desc_kaddr, *bitmap_kaddr;
  539. spinlock_t *lock;
  540. group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
  541. desc_kaddr = kmap(req->pr_desc_bh->b_page);
  542. desc = nilfs_palloc_block_get_group_desc(inode, group,
  543. req->pr_desc_bh, desc_kaddr);
  544. bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
  545. bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
  546. lock = nilfs_mdt_bgl_lock(inode, group);
  547. if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
  548. nilfs_warn(inode->i_sb,
  549. "%s (ino=%lu): entry number %llu already freed",
  550. __func__, inode->i_ino,
  551. (unsigned long long)req->pr_entry_nr);
  552. else
  553. nilfs_palloc_group_desc_add_entries(desc, lock, 1);
  554. kunmap(req->pr_bitmap_bh->b_page);
  555. kunmap(req->pr_desc_bh->b_page);
  556. mark_buffer_dirty(req->pr_desc_bh);
  557. mark_buffer_dirty(req->pr_bitmap_bh);
  558. nilfs_mdt_mark_dirty(inode);
  559. brelse(req->pr_bitmap_bh);
  560. brelse(req->pr_desc_bh);
  561. }
  562. /**
  563. * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
  564. * @inode: inode of metadata file using this allocator
  565. * @req: nilfs_palloc_req structure exchanged for the allocation
  566. */
  567. void nilfs_palloc_abort_alloc_entry(struct inode *inode,
  568. struct nilfs_palloc_req *req)
  569. {
  570. struct nilfs_palloc_group_desc *desc;
  571. void *desc_kaddr, *bitmap_kaddr;
  572. unsigned char *bitmap;
  573. unsigned long group, group_offset;
  574. spinlock_t *lock;
  575. group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
  576. desc_kaddr = kmap(req->pr_desc_bh->b_page);
  577. desc = nilfs_palloc_block_get_group_desc(inode, group,
  578. req->pr_desc_bh, desc_kaddr);
  579. bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
  580. bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
  581. lock = nilfs_mdt_bgl_lock(inode, group);
  582. if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
  583. nilfs_warn(inode->i_sb,
  584. "%s (ino=%lu): entry number %llu already freed",
  585. __func__, inode->i_ino,
  586. (unsigned long long)req->pr_entry_nr);
  587. else
  588. nilfs_palloc_group_desc_add_entries(desc, lock, 1);
  589. kunmap(req->pr_bitmap_bh->b_page);
  590. kunmap(req->pr_desc_bh->b_page);
  591. brelse(req->pr_bitmap_bh);
  592. brelse(req->pr_desc_bh);
  593. req->pr_entry_nr = 0;
  594. req->pr_bitmap_bh = NULL;
  595. req->pr_desc_bh = NULL;
  596. }
  597. /**
  598. * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
  599. * @inode: inode of metadata file using this allocator
  600. * @req: nilfs_palloc_req structure exchanged for the removal
  601. */
  602. int nilfs_palloc_prepare_free_entry(struct inode *inode,
  603. struct nilfs_palloc_req *req)
  604. {
  605. struct buffer_head *desc_bh, *bitmap_bh;
  606. unsigned long group, group_offset;
  607. int ret;
  608. group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
  609. ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
  610. if (ret < 0)
  611. return ret;
  612. ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
  613. if (ret < 0) {
  614. brelse(desc_bh);
  615. return ret;
  616. }
  617. req->pr_desc_bh = desc_bh;
  618. req->pr_bitmap_bh = bitmap_bh;
  619. return 0;
  620. }
  621. /**
  622. * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
  623. * @inode: inode of metadata file using this allocator
  624. * @req: nilfs_palloc_req structure exchanged for the removal
  625. */
  626. void nilfs_palloc_abort_free_entry(struct inode *inode,
  627. struct nilfs_palloc_req *req)
  628. {
  629. brelse(req->pr_bitmap_bh);
  630. brelse(req->pr_desc_bh);
  631. req->pr_entry_nr = 0;
  632. req->pr_bitmap_bh = NULL;
  633. req->pr_desc_bh = NULL;
  634. }
  635. /**
  636. * nilfs_palloc_freev - deallocate a set of persistent objects
  637. * @inode: inode of metadata file using this allocator
  638. * @entry_nrs: array of entry numbers to be deallocated
  639. * @nitems: number of entries stored in @entry_nrs
  640. */
  641. int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
  642. {
  643. struct buffer_head *desc_bh, *bitmap_bh;
  644. struct nilfs_palloc_group_desc *desc;
  645. unsigned char *bitmap;
  646. void *desc_kaddr, *bitmap_kaddr;
  647. unsigned long group, group_offset;
  648. __u64 group_min_nr, last_nrs[8];
  649. const unsigned long epg = nilfs_palloc_entries_per_group(inode);
  650. const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block;
  651. unsigned int entry_start, end, pos;
  652. spinlock_t *lock;
  653. int i, j, k, ret;
  654. u32 nfree;
  655. for (i = 0; i < nitems; i = j) {
  656. int change_group = false;
  657. int nempties = 0, n = 0;
  658. group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
  659. ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
  660. if (ret < 0)
  661. return ret;
  662. ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
  663. &bitmap_bh);
  664. if (ret < 0) {
  665. brelse(desc_bh);
  666. return ret;
  667. }
  668. /* Get the first entry number of the group */
  669. group_min_nr = (__u64)group * epg;
  670. bitmap_kaddr = kmap(bitmap_bh->b_page);
  671. bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
  672. lock = nilfs_mdt_bgl_lock(inode, group);
  673. j = i;
  674. entry_start = rounddown(group_offset, epb);
  675. do {
  676. if (!nilfs_clear_bit_atomic(lock, group_offset,
  677. bitmap)) {
  678. nilfs_warn(inode->i_sb,
  679. "%s (ino=%lu): entry number %llu already freed",
  680. __func__, inode->i_ino,
  681. (unsigned long long)entry_nrs[j]);
  682. } else {
  683. n++;
  684. }
  685. j++;
  686. if (j >= nitems || entry_nrs[j] < group_min_nr ||
  687. entry_nrs[j] >= group_min_nr + epg) {
  688. change_group = true;
  689. } else {
  690. group_offset = entry_nrs[j] - group_min_nr;
  691. if (group_offset >= entry_start &&
  692. group_offset < entry_start + epb) {
  693. /* This entry is in the same block */
  694. continue;
  695. }
  696. }
  697. /* Test if the entry block is empty or not */
  698. end = entry_start + epb;
  699. pos = nilfs_find_next_bit(bitmap, end, entry_start);
  700. if (pos >= end) {
  701. last_nrs[nempties++] = entry_nrs[j - 1];
  702. if (nempties >= ARRAY_SIZE(last_nrs))
  703. break;
  704. }
  705. if (change_group)
  706. break;
  707. /* Go on to the next entry block */
  708. entry_start = rounddown(group_offset, epb);
  709. } while (true);
  710. kunmap(bitmap_bh->b_page);
  711. mark_buffer_dirty(bitmap_bh);
  712. brelse(bitmap_bh);
  713. for (k = 0; k < nempties; k++) {
  714. ret = nilfs_palloc_delete_entry_block(inode,
  715. last_nrs[k]);
  716. if (ret && ret != -ENOENT)
  717. nilfs_warn(inode->i_sb,
  718. "error %d deleting block that object (entry=%llu, ino=%lu) belongs to",
  719. ret, (unsigned long long)last_nrs[k],
  720. inode->i_ino);
  721. }
  722. desc_kaddr = kmap_atomic(desc_bh->b_page);
  723. desc = nilfs_palloc_block_get_group_desc(
  724. inode, group, desc_bh, desc_kaddr);
  725. nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n);
  726. kunmap_atomic(desc_kaddr);
  727. mark_buffer_dirty(desc_bh);
  728. nilfs_mdt_mark_dirty(inode);
  729. brelse(desc_bh);
  730. if (nfree == nilfs_palloc_entries_per_group(inode)) {
  731. ret = nilfs_palloc_delete_bitmap_block(inode, group);
  732. if (ret && ret != -ENOENT)
  733. nilfs_warn(inode->i_sb,
  734. "error %d deleting bitmap block of group=%lu, ino=%lu",
  735. ret, group, inode->i_ino);
  736. }
  737. }
  738. return 0;
  739. }
  740. void nilfs_palloc_setup_cache(struct inode *inode,
  741. struct nilfs_palloc_cache *cache)
  742. {
  743. NILFS_MDT(inode)->mi_palloc_cache = cache;
  744. spin_lock_init(&cache->lock);
  745. }
  746. void nilfs_palloc_clear_cache(struct inode *inode)
  747. {
  748. struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
  749. spin_lock(&cache->lock);
  750. brelse(cache->prev_desc.bh);
  751. brelse(cache->prev_bitmap.bh);
  752. brelse(cache->prev_entry.bh);
  753. cache->prev_desc.bh = NULL;
  754. cache->prev_bitmap.bh = NULL;
  755. cache->prev_entry.bh = NULL;
  756. spin_unlock(&cache->lock);
  757. }
  758. void nilfs_palloc_destroy_cache(struct inode *inode)
  759. {
  760. nilfs_palloc_clear_cache(inode);
  761. NILFS_MDT(inode)->mi_palloc_cache = NULL;
  762. }