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   */
25  static inline unsigned long
nilfs_palloc_groups_per_desc_block(const struct inode * inode)26  nilfs_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   */
36  static inline unsigned long
nilfs_palloc_groups_count(const struct inode * inode)37  nilfs_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   */
nilfs_palloc_init_blockgroup(struct inode * inode,unsigned int entry_size)47  int 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   */
nilfs_palloc_group(const struct inode * inode,__u64 nr,unsigned long * offset)82  static 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   */
99  static unsigned long
nilfs_palloc_desc_blkoff(const struct inode * inode,unsigned long group)100  nilfs_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   */
115  static unsigned long
nilfs_palloc_bitmap_blkoff(const struct inode * inode,unsigned long group)116  nilfs_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   */
129  static unsigned long
nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc * desc,spinlock_t * lock)130  nilfs_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   */
147  static u32
nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc * desc,spinlock_t * lock,u32 n)148  nilfs_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   */
165  static unsigned long
nilfs_palloc_entry_blkoff(const struct inode * inode,__u64 nr)166  nilfs_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   */
nilfs_palloc_desc_block_init(struct inode * inode,struct buffer_head * bh,void * kaddr)182  static 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  
nilfs_palloc_get_block(struct inode * inode,unsigned long blkoff,int create,void (* init_block)(struct inode *,struct buffer_head *,void *),struct buffer_head ** bhp,struct nilfs_bh_assoc * prev,spinlock_t * lock)196  static 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  	    likely(buffer_uptodate(prev->bh))) {
210  		get_bh(prev->bh);
211  		*bhp = prev->bh;
212  		spin_unlock(lock);
213  		return 0;
214  	}
215  	spin_unlock(lock);
216  
217  	ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp);
218  	if (!ret) {
219  		spin_lock(lock);
220  		/*
221  		 * The following code must be safe for change of the
222  		 * cache contents during the get block call.
223  		 */
224  		brelse(prev->bh);
225  		get_bh(*bhp);
226  		prev->bh = *bhp;
227  		prev->blkoff = blkoff;
228  		spin_unlock(lock);
229  	}
230  	return ret;
231  }
232  
233  /**
234   * nilfs_palloc_delete_block - delete a block on the persistent allocator file
235   * @inode: inode of metadata file using this allocator
236   * @blkoff: block offset
237   * @prev: nilfs_bh_assoc struct of the last used buffer
238   * @lock: spin lock protecting @prev
239   */
nilfs_palloc_delete_block(struct inode * inode,unsigned long blkoff,struct nilfs_bh_assoc * prev,spinlock_t * lock)240  static int nilfs_palloc_delete_block(struct inode *inode, unsigned long blkoff,
241  				     struct nilfs_bh_assoc *prev,
242  				     spinlock_t *lock)
243  {
244  	spin_lock(lock);
245  	if (prev->bh && blkoff == prev->blkoff) {
246  		brelse(prev->bh);
247  		prev->bh = NULL;
248  	}
249  	spin_unlock(lock);
250  	return nilfs_mdt_delete_block(inode, blkoff);
251  }
252  
253  /**
254   * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block
255   * @inode: inode of metadata file using this allocator
256   * @group: group number
257   * @create: create flag
258   * @bhp: pointer to store the resultant buffer head
259   */
nilfs_palloc_get_desc_block(struct inode * inode,unsigned long group,int create,struct buffer_head ** bhp)260  static int nilfs_palloc_get_desc_block(struct inode *inode,
261  				       unsigned long group,
262  				       int create, struct buffer_head **bhp)
263  {
264  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
265  
266  	return nilfs_palloc_get_block(inode,
267  				      nilfs_palloc_desc_blkoff(inode, group),
268  				      create, nilfs_palloc_desc_block_init,
269  				      bhp, &cache->prev_desc, &cache->lock);
270  }
271  
272  /**
273   * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block
274   * @inode: inode of metadata file using this allocator
275   * @group: group number
276   * @create: create flag
277   * @bhp: pointer to store the resultant buffer head
278   */
nilfs_palloc_get_bitmap_block(struct inode * inode,unsigned long group,int create,struct buffer_head ** bhp)279  static int nilfs_palloc_get_bitmap_block(struct inode *inode,
280  					 unsigned long group,
281  					 int create, struct buffer_head **bhp)
282  {
283  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
284  
285  	return nilfs_palloc_get_block(inode,
286  				      nilfs_palloc_bitmap_blkoff(inode, group),
287  				      create, NULL, bhp,
288  				      &cache->prev_bitmap, &cache->lock);
289  }
290  
291  /**
292   * nilfs_palloc_delete_bitmap_block - delete a bitmap block
293   * @inode: inode of metadata file using this allocator
294   * @group: group number
295   */
nilfs_palloc_delete_bitmap_block(struct inode * inode,unsigned long group)296  static int nilfs_palloc_delete_bitmap_block(struct inode *inode,
297  					    unsigned long group)
298  {
299  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
300  
301  	return nilfs_palloc_delete_block(inode,
302  					 nilfs_palloc_bitmap_blkoff(inode,
303  								    group),
304  					 &cache->prev_bitmap, &cache->lock);
305  }
306  
307  /**
308   * nilfs_palloc_get_entry_block - get buffer head of an entry block
309   * @inode: inode of metadata file using this allocator
310   * @nr: serial number of the entry (e.g. inode number)
311   * @create: create flag
312   * @bhp: pointer to store the resultant buffer head
313   */
nilfs_palloc_get_entry_block(struct inode * inode,__u64 nr,int create,struct buffer_head ** bhp)314  int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
315  				 int create, struct buffer_head **bhp)
316  {
317  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
318  
319  	return nilfs_palloc_get_block(inode,
320  				      nilfs_palloc_entry_blkoff(inode, nr),
321  				      create, NULL, bhp,
322  				      &cache->prev_entry, &cache->lock);
323  }
324  
325  /**
326   * nilfs_palloc_delete_entry_block - delete an entry block
327   * @inode: inode of metadata file using this allocator
328   * @nr: serial number of the entry
329   */
nilfs_palloc_delete_entry_block(struct inode * inode,__u64 nr)330  static int nilfs_palloc_delete_entry_block(struct inode *inode, __u64 nr)
331  {
332  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
333  
334  	return nilfs_palloc_delete_block(inode,
335  					 nilfs_palloc_entry_blkoff(inode, nr),
336  					 &cache->prev_entry, &cache->lock);
337  }
338  
339  /**
340   * nilfs_palloc_block_get_group_desc - get kernel address of a group descriptor
341   * @inode: inode of metadata file using this allocator
342   * @group: group number
343   * @bh: buffer head of the buffer storing the group descriptor block
344   * @kaddr: kernel address mapped for the page including the buffer
345   */
346  static struct nilfs_palloc_group_desc *
nilfs_palloc_block_get_group_desc(const struct inode * inode,unsigned long group,const struct buffer_head * bh,void * kaddr)347  nilfs_palloc_block_get_group_desc(const struct inode *inode,
348  				  unsigned long group,
349  				  const struct buffer_head *bh, void *kaddr)
350  {
351  	return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
352  		group % nilfs_palloc_groups_per_desc_block(inode);
353  }
354  
355  /**
356   * nilfs_palloc_block_get_entry - get kernel address of an entry
357   * @inode: inode of metadata file using this allocator
358   * @nr: serial number of the entry (e.g. inode number)
359   * @bh: buffer head of the buffer storing the entry block
360   * @kaddr: kernel address mapped for the page including the buffer
361   */
nilfs_palloc_block_get_entry(const struct inode * inode,__u64 nr,const struct buffer_head * bh,void * kaddr)362  void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
363  				   const struct buffer_head *bh, void *kaddr)
364  {
365  	unsigned long entry_offset, group_offset;
366  
367  	nilfs_palloc_group(inode, nr, &group_offset);
368  	entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
369  
370  	return kaddr + bh_offset(bh) +
371  		entry_offset * NILFS_MDT(inode)->mi_entry_size;
372  }
373  
374  /**
375   * nilfs_palloc_find_available_slot - find available slot in a group
376   * @bitmap: bitmap of the group
377   * @target: offset number of an entry in the group (start point)
378   * @bsize: size in bits
379   * @lock: spin lock protecting @bitmap
380   * @wrap: whether to wrap around
381   */
nilfs_palloc_find_available_slot(unsigned char * bitmap,unsigned long target,unsigned int bsize,spinlock_t * lock,bool wrap)382  static int nilfs_palloc_find_available_slot(unsigned char *bitmap,
383  					    unsigned long target,
384  					    unsigned int bsize,
385  					    spinlock_t *lock, bool wrap)
386  {
387  	int pos, end = bsize;
388  
389  	if (likely(target < bsize)) {
390  		pos = target;
391  		do {
392  			pos = nilfs_find_next_zero_bit(bitmap, end, pos);
393  			if (pos >= end)
394  				break;
395  			if (!nilfs_set_bit_atomic(lock, pos, bitmap))
396  				return pos;
397  		} while (++pos < end);
398  
399  		end = target;
400  	}
401  	if (!wrap)
402  		return -ENOSPC;
403  
404  	/* wrap around */
405  	for (pos = 0; pos < end; pos++) {
406  		pos = nilfs_find_next_zero_bit(bitmap, end, pos);
407  		if (pos >= end)
408  			break;
409  		if (!nilfs_set_bit_atomic(lock, pos, bitmap))
410  			return pos;
411  	}
412  
413  	return -ENOSPC;
414  }
415  
416  /**
417   * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups
418   *					    in a group descriptor block
419   * @inode: inode of metadata file using this allocator
420   * @curr: current group number
421   * @max: maximum number of groups
422   */
423  static unsigned long
nilfs_palloc_rest_groups_in_desc_block(const struct inode * inode,unsigned long curr,unsigned long max)424  nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
425  				       unsigned long curr, unsigned long max)
426  {
427  	return min_t(unsigned long,
428  		     nilfs_palloc_groups_per_desc_block(inode) -
429  		     curr % nilfs_palloc_groups_per_desc_block(inode),
430  		     max - curr + 1);
431  }
432  
433  /**
434   * nilfs_palloc_count_desc_blocks - count descriptor blocks number
435   * @inode: inode of metadata file using this allocator
436   * @desc_blocks: descriptor blocks number [out]
437   */
nilfs_palloc_count_desc_blocks(struct inode * inode,unsigned long * desc_blocks)438  static int nilfs_palloc_count_desc_blocks(struct inode *inode,
439  					    unsigned long *desc_blocks)
440  {
441  	__u64 blknum;
442  	int ret;
443  
444  	ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum);
445  	if (likely(!ret))
446  		*desc_blocks = DIV_ROUND_UP(
447  			(unsigned long)blknum,
448  			NILFS_MDT(inode)->mi_blocks_per_desc_block);
449  	return ret;
450  }
451  
452  /**
453   * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
454   *					MDT file growing
455   * @inode: inode of metadata file using this allocator
456   * @desc_blocks: known current descriptor blocks count
457   */
nilfs_palloc_mdt_file_can_grow(struct inode * inode,unsigned long desc_blocks)458  static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
459  						    unsigned long desc_blocks)
460  {
461  	return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) <
462  			nilfs_palloc_groups_count(inode);
463  }
464  
465  /**
466   * nilfs_palloc_count_max_entries - count max number of entries that can be
467   *					described by descriptor blocks count
468   * @inode: inode of metadata file using this allocator
469   * @nused: current number of used entries
470   * @nmaxp: max number of entries [out]
471   */
nilfs_palloc_count_max_entries(struct inode * inode,u64 nused,u64 * nmaxp)472  int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
473  {
474  	unsigned long desc_blocks = 0;
475  	u64 entries_per_desc_block, nmax;
476  	int err;
477  
478  	err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks);
479  	if (unlikely(err))
480  		return err;
481  
482  	entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
483  				nilfs_palloc_groups_per_desc_block(inode);
484  	nmax = entries_per_desc_block * desc_blocks;
485  
486  	if (nused == nmax &&
487  			nilfs_palloc_mdt_file_can_grow(inode, desc_blocks))
488  		nmax += entries_per_desc_block;
489  
490  	if (nused > nmax)
491  		return -ERANGE;
492  
493  	*nmaxp = nmax;
494  	return 0;
495  }
496  
497  /**
498   * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
499   * @inode: inode of metadata file using this allocator
500   * @req: nilfs_palloc_req structure exchanged for the allocation
501   * @wrap: whether to wrap around
502   */
nilfs_palloc_prepare_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req,bool wrap)503  int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
504  				     struct nilfs_palloc_req *req, bool wrap)
505  {
506  	struct buffer_head *desc_bh, *bitmap_bh;
507  	struct nilfs_palloc_group_desc *desc;
508  	unsigned char *bitmap;
509  	void *desc_kaddr, *bitmap_kaddr;
510  	unsigned long group, maxgroup, ngroups;
511  	unsigned long group_offset, maxgroup_offset;
512  	unsigned long n, entries_per_group;
513  	unsigned long i, j;
514  	spinlock_t *lock;
515  	int pos, ret;
516  
517  	ngroups = nilfs_palloc_groups_count(inode);
518  	maxgroup = ngroups - 1;
519  	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
520  	entries_per_group = nilfs_palloc_entries_per_group(inode);
521  
522  	for (i = 0; i < ngroups; i += n) {
523  		if (group >= ngroups && wrap) {
524  			/* wrap around */
525  			group = 0;
526  			maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
527  						      &maxgroup_offset) - 1;
528  		}
529  		ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
530  		if (ret < 0)
531  			return ret;
532  		desc_kaddr = kmap_local_page(desc_bh->b_page);
533  		desc = nilfs_palloc_block_get_group_desc(
534  			inode, group, desc_bh, desc_kaddr);
535  		n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
536  							   maxgroup);
537  		for (j = 0; j < n; j++, desc++, group++, group_offset = 0) {
538  			lock = nilfs_mdt_bgl_lock(inode, group);
539  			if (nilfs_palloc_group_desc_nfrees(desc, lock) == 0)
540  				continue;
541  
542  			kunmap_local(desc_kaddr);
543  			ret = nilfs_palloc_get_bitmap_block(inode, group, 1,
544  							    &bitmap_bh);
545  			if (unlikely(ret < 0)) {
546  				brelse(desc_bh);
547  				return ret;
548  			}
549  
550  			desc_kaddr = kmap_local_page(desc_bh->b_page);
551  			desc = nilfs_palloc_block_get_group_desc(
552  				inode, group, desc_bh, desc_kaddr);
553  
554  			bitmap_kaddr = kmap_local_page(bitmap_bh->b_page);
555  			bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
556  			pos = nilfs_palloc_find_available_slot(
557  				bitmap, group_offset, entries_per_group, lock,
558  				wrap);
559  			/*
560  			 * Since the search for a free slot in the second and
561  			 * subsequent bitmap blocks always starts from the
562  			 * beginning, the wrap flag only has an effect on the
563  			 * first search.
564  			 */
565  			kunmap_local(bitmap_kaddr);
566  			if (pos >= 0)
567  				goto found;
568  
569  			brelse(bitmap_bh);
570  		}
571  
572  		kunmap_local(desc_kaddr);
573  		brelse(desc_bh);
574  	}
575  
576  	/* no entries left */
577  	return -ENOSPC;
578  
579  found:
580  	/* found a free entry */
581  	nilfs_palloc_group_desc_add_entries(desc, lock, -1);
582  	req->pr_entry_nr = entries_per_group * group + pos;
583  	kunmap_local(desc_kaddr);
584  
585  	req->pr_desc_bh = desc_bh;
586  	req->pr_bitmap_bh = bitmap_bh;
587  	return 0;
588  }
589  
590  /**
591   * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
592   * @inode: inode of metadata file using this allocator
593   * @req: nilfs_palloc_req structure exchanged for the allocation
594   */
nilfs_palloc_commit_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req)595  void nilfs_palloc_commit_alloc_entry(struct inode *inode,
596  				     struct nilfs_palloc_req *req)
597  {
598  	mark_buffer_dirty(req->pr_bitmap_bh);
599  	mark_buffer_dirty(req->pr_desc_bh);
600  	nilfs_mdt_mark_dirty(inode);
601  
602  	brelse(req->pr_bitmap_bh);
603  	brelse(req->pr_desc_bh);
604  }
605  
606  /**
607   * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
608   * @inode: inode of metadata file using this allocator
609   * @req: nilfs_palloc_req structure exchanged for the removal
610   */
nilfs_palloc_commit_free_entry(struct inode * inode,struct nilfs_palloc_req * req)611  void nilfs_palloc_commit_free_entry(struct inode *inode,
612  				    struct nilfs_palloc_req *req)
613  {
614  	struct nilfs_palloc_group_desc *desc;
615  	unsigned long group, group_offset;
616  	unsigned char *bitmap;
617  	void *desc_kaddr, *bitmap_kaddr;
618  	spinlock_t *lock;
619  
620  	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
621  	desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page);
622  	desc = nilfs_palloc_block_get_group_desc(inode, group,
623  						 req->pr_desc_bh, desc_kaddr);
624  	bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page);
625  	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
626  	lock = nilfs_mdt_bgl_lock(inode, group);
627  
628  	if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
629  		nilfs_warn(inode->i_sb,
630  			   "%s (ino=%lu): entry number %llu already freed",
631  			   __func__, inode->i_ino,
632  			   (unsigned long long)req->pr_entry_nr);
633  	else
634  		nilfs_palloc_group_desc_add_entries(desc, lock, 1);
635  
636  	kunmap_local(bitmap_kaddr);
637  	kunmap_local(desc_kaddr);
638  
639  	mark_buffer_dirty(req->pr_desc_bh);
640  	mark_buffer_dirty(req->pr_bitmap_bh);
641  	nilfs_mdt_mark_dirty(inode);
642  
643  	brelse(req->pr_bitmap_bh);
644  	brelse(req->pr_desc_bh);
645  }
646  
647  /**
648   * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
649   * @inode: inode of metadata file using this allocator
650   * @req: nilfs_palloc_req structure exchanged for the allocation
651   */
nilfs_palloc_abort_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req)652  void nilfs_palloc_abort_alloc_entry(struct inode *inode,
653  				    struct nilfs_palloc_req *req)
654  {
655  	struct nilfs_palloc_group_desc *desc;
656  	void *desc_kaddr, *bitmap_kaddr;
657  	unsigned char *bitmap;
658  	unsigned long group, group_offset;
659  	spinlock_t *lock;
660  
661  	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
662  	desc_kaddr = kmap_local_page(req->pr_desc_bh->b_page);
663  	desc = nilfs_palloc_block_get_group_desc(inode, group,
664  						 req->pr_desc_bh, desc_kaddr);
665  	bitmap_kaddr = kmap_local_page(req->pr_bitmap_bh->b_page);
666  	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
667  	lock = nilfs_mdt_bgl_lock(inode, group);
668  
669  	if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
670  		nilfs_warn(inode->i_sb,
671  			   "%s (ino=%lu): entry number %llu already freed",
672  			   __func__, inode->i_ino,
673  			   (unsigned long long)req->pr_entry_nr);
674  	else
675  		nilfs_palloc_group_desc_add_entries(desc, lock, 1);
676  
677  	kunmap_local(bitmap_kaddr);
678  	kunmap_local(desc_kaddr);
679  
680  	brelse(req->pr_bitmap_bh);
681  	brelse(req->pr_desc_bh);
682  
683  	req->pr_entry_nr = 0;
684  	req->pr_bitmap_bh = NULL;
685  	req->pr_desc_bh = NULL;
686  }
687  
688  /**
689   * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
690   * @inode: inode of metadata file using this allocator
691   * @req: nilfs_palloc_req structure exchanged for the removal
692   */
nilfs_palloc_prepare_free_entry(struct inode * inode,struct nilfs_palloc_req * req)693  int nilfs_palloc_prepare_free_entry(struct inode *inode,
694  				    struct nilfs_palloc_req *req)
695  {
696  	struct buffer_head *desc_bh, *bitmap_bh;
697  	unsigned long group, group_offset;
698  	int ret;
699  
700  	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
701  	ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
702  	if (ret < 0)
703  		return ret;
704  	ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
705  	if (ret < 0) {
706  		brelse(desc_bh);
707  		return ret;
708  	}
709  
710  	req->pr_desc_bh = desc_bh;
711  	req->pr_bitmap_bh = bitmap_bh;
712  	return 0;
713  }
714  
715  /**
716   * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
717   * @inode: inode of metadata file using this allocator
718   * @req: nilfs_palloc_req structure exchanged for the removal
719   */
nilfs_palloc_abort_free_entry(struct inode * inode,struct nilfs_palloc_req * req)720  void nilfs_palloc_abort_free_entry(struct inode *inode,
721  				   struct nilfs_palloc_req *req)
722  {
723  	brelse(req->pr_bitmap_bh);
724  	brelse(req->pr_desc_bh);
725  
726  	req->pr_entry_nr = 0;
727  	req->pr_bitmap_bh = NULL;
728  	req->pr_desc_bh = NULL;
729  }
730  
731  /**
732   * nilfs_palloc_freev - deallocate a set of persistent objects
733   * @inode: inode of metadata file using this allocator
734   * @entry_nrs: array of entry numbers to be deallocated
735   * @nitems: number of entries stored in @entry_nrs
736   */
nilfs_palloc_freev(struct inode * inode,__u64 * entry_nrs,size_t nitems)737  int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
738  {
739  	struct buffer_head *desc_bh, *bitmap_bh;
740  	struct nilfs_palloc_group_desc *desc;
741  	unsigned char *bitmap;
742  	void *desc_kaddr, *bitmap_kaddr;
743  	unsigned long group, group_offset;
744  	__u64 group_min_nr, last_nrs[8];
745  	const unsigned long epg = nilfs_palloc_entries_per_group(inode);
746  	const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block;
747  	unsigned int entry_start, end, pos;
748  	spinlock_t *lock;
749  	int i, j, k, ret;
750  	u32 nfree;
751  
752  	for (i = 0; i < nitems; i = j) {
753  		int change_group = false;
754  		int nempties = 0, n = 0;
755  
756  		group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
757  		ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
758  		if (ret < 0)
759  			return ret;
760  		ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
761  						    &bitmap_bh);
762  		if (ret < 0) {
763  			brelse(desc_bh);
764  			return ret;
765  		}
766  
767  		/* Get the first entry number of the group */
768  		group_min_nr = (__u64)group * epg;
769  
770  		bitmap_kaddr = kmap_local_page(bitmap_bh->b_page);
771  		bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
772  		lock = nilfs_mdt_bgl_lock(inode, group);
773  
774  		j = i;
775  		entry_start = rounddown(group_offset, epb);
776  		do {
777  			if (!nilfs_clear_bit_atomic(lock, group_offset,
778  						    bitmap)) {
779  				nilfs_warn(inode->i_sb,
780  					   "%s (ino=%lu): entry number %llu already freed",
781  					   __func__, inode->i_ino,
782  					   (unsigned long long)entry_nrs[j]);
783  			} else {
784  				n++;
785  			}
786  
787  			j++;
788  			if (j >= nitems || entry_nrs[j] < group_min_nr ||
789  			    entry_nrs[j] >= group_min_nr + epg) {
790  				change_group = true;
791  			} else {
792  				group_offset = entry_nrs[j] - group_min_nr;
793  				if (group_offset >= entry_start &&
794  				    group_offset < entry_start + epb) {
795  					/* This entry is in the same block */
796  					continue;
797  				}
798  			}
799  
800  			/* Test if the entry block is empty or not */
801  			end = entry_start + epb;
802  			pos = nilfs_find_next_bit(bitmap, end, entry_start);
803  			if (pos >= end) {
804  				last_nrs[nempties++] = entry_nrs[j - 1];
805  				if (nempties >= ARRAY_SIZE(last_nrs))
806  					break;
807  			}
808  
809  			if (change_group)
810  				break;
811  
812  			/* Go on to the next entry block */
813  			entry_start = rounddown(group_offset, epb);
814  		} while (true);
815  
816  		kunmap_local(bitmap_kaddr);
817  		mark_buffer_dirty(bitmap_bh);
818  		brelse(bitmap_bh);
819  
820  		for (k = 0; k < nempties; k++) {
821  			ret = nilfs_palloc_delete_entry_block(inode,
822  							      last_nrs[k]);
823  			if (ret && ret != -ENOENT)
824  				nilfs_warn(inode->i_sb,
825  					   "error %d deleting block that object (entry=%llu, ino=%lu) belongs to",
826  					   ret, (unsigned long long)last_nrs[k],
827  					   inode->i_ino);
828  		}
829  
830  		desc_kaddr = kmap_local_page(desc_bh->b_page);
831  		desc = nilfs_palloc_block_get_group_desc(
832  			inode, group, desc_bh, desc_kaddr);
833  		nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n);
834  		kunmap_local(desc_kaddr);
835  		mark_buffer_dirty(desc_bh);
836  		nilfs_mdt_mark_dirty(inode);
837  		brelse(desc_bh);
838  
839  		if (nfree == nilfs_palloc_entries_per_group(inode)) {
840  			ret = nilfs_palloc_delete_bitmap_block(inode, group);
841  			if (ret && ret != -ENOENT)
842  				nilfs_warn(inode->i_sb,
843  					   "error %d deleting bitmap block of group=%lu, ino=%lu",
844  					   ret, group, inode->i_ino);
845  		}
846  	}
847  	return 0;
848  }
849  
nilfs_palloc_setup_cache(struct inode * inode,struct nilfs_palloc_cache * cache)850  void nilfs_palloc_setup_cache(struct inode *inode,
851  			      struct nilfs_palloc_cache *cache)
852  {
853  	NILFS_MDT(inode)->mi_palloc_cache = cache;
854  	spin_lock_init(&cache->lock);
855  }
856  
nilfs_palloc_clear_cache(struct inode * inode)857  void nilfs_palloc_clear_cache(struct inode *inode)
858  {
859  	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
860  
861  	spin_lock(&cache->lock);
862  	brelse(cache->prev_desc.bh);
863  	brelse(cache->prev_bitmap.bh);
864  	brelse(cache->prev_entry.bh);
865  	cache->prev_desc.bh = NULL;
866  	cache->prev_bitmap.bh = NULL;
867  	cache->prev_entry.bh = NULL;
868  	spin_unlock(&cache->lock);
869  }
870  
nilfs_palloc_destroy_cache(struct inode * inode)871  void nilfs_palloc_destroy_cache(struct inode *inode)
872  {
873  	nilfs_palloc_clear_cache(inode);
874  	NILFS_MDT(inode)->mi_palloc_cache = NULL;
875  }
876