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