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 
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  */
nilfs_palloc_find_available_slot(unsigned char * bitmap,unsigned long target,unsigned int bsize,spinlock_t * lock)381 static int nilfs_palloc_find_available_slot(unsigned char *bitmap,
382 					    unsigned long target,
383 					    unsigned int bsize,
384 					    spinlock_t *lock)
385 {
386 	int pos, end = bsize;
387 
388 	if (likely(target < bsize)) {
389 		pos = target;
390 		do {
391 			pos = nilfs_find_next_zero_bit(bitmap, end, pos);
392 			if (pos >= end)
393 				break;
394 			if (!nilfs_set_bit_atomic(lock, pos, bitmap))
395 				return pos;
396 		} while (++pos < end);
397 
398 		end = target;
399 	}
400 
401 	/* wrap around */
402 	for (pos = 0; pos < end; pos++) {
403 		pos = nilfs_find_next_zero_bit(bitmap, end, pos);
404 		if (pos >= end)
405 			break;
406 		if (!nilfs_set_bit_atomic(lock, pos, bitmap))
407 			return pos;
408 	}
409 
410 	return -ENOSPC;
411 }
412 
413 /**
414  * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups
415  *					    in a group descriptor block
416  * @inode: inode of metadata file using this allocator
417  * @curr: current group number
418  * @max: maximum number of groups
419  */
420 static unsigned long
nilfs_palloc_rest_groups_in_desc_block(const struct inode * inode,unsigned long curr,unsigned long max)421 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
422 				       unsigned long curr, unsigned long max)
423 {
424 	return min_t(unsigned long,
425 		     nilfs_palloc_groups_per_desc_block(inode) -
426 		     curr % nilfs_palloc_groups_per_desc_block(inode),
427 		     max - curr + 1);
428 }
429 
430 /**
431  * nilfs_palloc_count_desc_blocks - count descriptor blocks number
432  * @inode: inode of metadata file using this allocator
433  * @desc_blocks: descriptor blocks number [out]
434  */
nilfs_palloc_count_desc_blocks(struct inode * inode,unsigned long * desc_blocks)435 static int nilfs_palloc_count_desc_blocks(struct inode *inode,
436 					    unsigned long *desc_blocks)
437 {
438 	__u64 blknum;
439 	int ret;
440 
441 	ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum);
442 	if (likely(!ret))
443 		*desc_blocks = DIV_ROUND_UP(
444 			(unsigned long)blknum,
445 			NILFS_MDT(inode)->mi_blocks_per_desc_block);
446 	return ret;
447 }
448 
449 /**
450  * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
451  *					MDT file growing
452  * @inode: inode of metadata file using this allocator
453  * @desc_blocks: known current descriptor blocks count
454  */
nilfs_palloc_mdt_file_can_grow(struct inode * inode,unsigned long desc_blocks)455 static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
456 						    unsigned long desc_blocks)
457 {
458 	return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) <
459 			nilfs_palloc_groups_count(inode);
460 }
461 
462 /**
463  * nilfs_palloc_count_max_entries - count max number of entries that can be
464  *					described by descriptor blocks count
465  * @inode: inode of metadata file using this allocator
466  * @nused: current number of used entries
467  * @nmaxp: max number of entries [out]
468  */
nilfs_palloc_count_max_entries(struct inode * inode,u64 nused,u64 * nmaxp)469 int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
470 {
471 	unsigned long desc_blocks = 0;
472 	u64 entries_per_desc_block, nmax;
473 	int err;
474 
475 	err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks);
476 	if (unlikely(err))
477 		return err;
478 
479 	entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
480 				nilfs_palloc_groups_per_desc_block(inode);
481 	nmax = entries_per_desc_block * desc_blocks;
482 
483 	if (nused == nmax &&
484 			nilfs_palloc_mdt_file_can_grow(inode, desc_blocks))
485 		nmax += entries_per_desc_block;
486 
487 	if (nused > nmax)
488 		return -ERANGE;
489 
490 	*nmaxp = nmax;
491 	return 0;
492 }
493 
494 /**
495  * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
496  * @inode: inode of metadata file using this allocator
497  * @req: nilfs_palloc_req structure exchanged for the allocation
498  */
nilfs_palloc_prepare_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req)499 int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
500 				     struct nilfs_palloc_req *req)
501 {
502 	struct buffer_head *desc_bh, *bitmap_bh;
503 	struct nilfs_palloc_group_desc *desc;
504 	unsigned char *bitmap;
505 	void *desc_kaddr, *bitmap_kaddr;
506 	unsigned long group, maxgroup, ngroups;
507 	unsigned long group_offset, maxgroup_offset;
508 	unsigned long n, entries_per_group;
509 	unsigned long i, j;
510 	spinlock_t *lock;
511 	int pos, ret;
512 
513 	ngroups = nilfs_palloc_groups_count(inode);
514 	maxgroup = ngroups - 1;
515 	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
516 	entries_per_group = nilfs_palloc_entries_per_group(inode);
517 
518 	for (i = 0; i < ngroups; i += n) {
519 		if (group >= ngroups) {
520 			/* wrap around */
521 			group = 0;
522 			maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
523 						      &maxgroup_offset) - 1;
524 		}
525 		ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
526 		if (ret < 0)
527 			return ret;
528 		desc_kaddr = kmap(desc_bh->b_page);
529 		desc = nilfs_palloc_block_get_group_desc(
530 			inode, group, desc_bh, desc_kaddr);
531 		n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
532 							   maxgroup);
533 		for (j = 0; j < n; j++, desc++, group++) {
534 			lock = nilfs_mdt_bgl_lock(inode, group);
535 			if (nilfs_palloc_group_desc_nfrees(desc, lock) > 0) {
536 				ret = nilfs_palloc_get_bitmap_block(
537 					inode, group, 1, &bitmap_bh);
538 				if (ret < 0)
539 					goto out_desc;
540 				bitmap_kaddr = kmap(bitmap_bh->b_page);
541 				bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
542 				pos = nilfs_palloc_find_available_slot(
543 					bitmap, group_offset,
544 					entries_per_group, lock);
545 				if (pos >= 0) {
546 					/* found a free entry */
547 					nilfs_palloc_group_desc_add_entries(
548 						desc, lock, -1);
549 					req->pr_entry_nr =
550 						entries_per_group * group + pos;
551 					kunmap(desc_bh->b_page);
552 					kunmap(bitmap_bh->b_page);
553 
554 					req->pr_desc_bh = desc_bh;
555 					req->pr_bitmap_bh = bitmap_bh;
556 					return 0;
557 				}
558 				kunmap(bitmap_bh->b_page);
559 				brelse(bitmap_bh);
560 			}
561 
562 			group_offset = 0;
563 		}
564 
565 		kunmap(desc_bh->b_page);
566 		brelse(desc_bh);
567 	}
568 
569 	/* no entries left */
570 	return -ENOSPC;
571 
572  out_desc:
573 	kunmap(desc_bh->b_page);
574 	brelse(desc_bh);
575 	return ret;
576 }
577 
578 /**
579  * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
580  * @inode: inode of metadata file using this allocator
581  * @req: nilfs_palloc_req structure exchanged for the allocation
582  */
nilfs_palloc_commit_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req)583 void nilfs_palloc_commit_alloc_entry(struct inode *inode,
584 				     struct nilfs_palloc_req *req)
585 {
586 	mark_buffer_dirty(req->pr_bitmap_bh);
587 	mark_buffer_dirty(req->pr_desc_bh);
588 	nilfs_mdt_mark_dirty(inode);
589 
590 	brelse(req->pr_bitmap_bh);
591 	brelse(req->pr_desc_bh);
592 }
593 
594 /**
595  * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
596  * @inode: inode of metadata file using this allocator
597  * @req: nilfs_palloc_req structure exchanged for the removal
598  */
nilfs_palloc_commit_free_entry(struct inode * inode,struct nilfs_palloc_req * req)599 void nilfs_palloc_commit_free_entry(struct inode *inode,
600 				    struct nilfs_palloc_req *req)
601 {
602 	struct nilfs_palloc_group_desc *desc;
603 	unsigned long group, group_offset;
604 	unsigned char *bitmap;
605 	void *desc_kaddr, *bitmap_kaddr;
606 	spinlock_t *lock;
607 
608 	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
609 	desc_kaddr = kmap(req->pr_desc_bh->b_page);
610 	desc = nilfs_palloc_block_get_group_desc(inode, group,
611 						 req->pr_desc_bh, desc_kaddr);
612 	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
613 	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
614 	lock = nilfs_mdt_bgl_lock(inode, group);
615 
616 	if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
617 		nilfs_msg(inode->i_sb, KERN_WARNING,
618 			  "%s (ino=%lu): entry number %llu already freed",
619 			  __func__, inode->i_ino,
620 			  (unsigned long long)req->pr_entry_nr);
621 	else
622 		nilfs_palloc_group_desc_add_entries(desc, lock, 1);
623 
624 	kunmap(req->pr_bitmap_bh->b_page);
625 	kunmap(req->pr_desc_bh->b_page);
626 
627 	mark_buffer_dirty(req->pr_desc_bh);
628 	mark_buffer_dirty(req->pr_bitmap_bh);
629 	nilfs_mdt_mark_dirty(inode);
630 
631 	brelse(req->pr_bitmap_bh);
632 	brelse(req->pr_desc_bh);
633 }
634 
635 /**
636  * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
637  * @inode: inode of metadata file using this allocator
638  * @req: nilfs_palloc_req structure exchanged for the allocation
639  */
nilfs_palloc_abort_alloc_entry(struct inode * inode,struct nilfs_palloc_req * req)640 void nilfs_palloc_abort_alloc_entry(struct inode *inode,
641 				    struct nilfs_palloc_req *req)
642 {
643 	struct nilfs_palloc_group_desc *desc;
644 	void *desc_kaddr, *bitmap_kaddr;
645 	unsigned char *bitmap;
646 	unsigned long group, group_offset;
647 	spinlock_t *lock;
648 
649 	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
650 	desc_kaddr = kmap(req->pr_desc_bh->b_page);
651 	desc = nilfs_palloc_block_get_group_desc(inode, group,
652 						 req->pr_desc_bh, desc_kaddr);
653 	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
654 	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
655 	lock = nilfs_mdt_bgl_lock(inode, group);
656 
657 	if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
658 		nilfs_msg(inode->i_sb, KERN_WARNING,
659 			  "%s (ino=%lu): entry number %llu already freed",
660 			  __func__, inode->i_ino,
661 			  (unsigned long long)req->pr_entry_nr);
662 	else
663 		nilfs_palloc_group_desc_add_entries(desc, lock, 1);
664 
665 	kunmap(req->pr_bitmap_bh->b_page);
666 	kunmap(req->pr_desc_bh->b_page);
667 
668 	brelse(req->pr_bitmap_bh);
669 	brelse(req->pr_desc_bh);
670 
671 	req->pr_entry_nr = 0;
672 	req->pr_bitmap_bh = NULL;
673 	req->pr_desc_bh = NULL;
674 }
675 
676 /**
677  * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
678  * @inode: inode of metadata file using this allocator
679  * @req: nilfs_palloc_req structure exchanged for the removal
680  */
nilfs_palloc_prepare_free_entry(struct inode * inode,struct nilfs_palloc_req * req)681 int nilfs_palloc_prepare_free_entry(struct inode *inode,
682 				    struct nilfs_palloc_req *req)
683 {
684 	struct buffer_head *desc_bh, *bitmap_bh;
685 	unsigned long group, group_offset;
686 	int ret;
687 
688 	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
689 	ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
690 	if (ret < 0)
691 		return ret;
692 	ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
693 	if (ret < 0) {
694 		brelse(desc_bh);
695 		return ret;
696 	}
697 
698 	req->pr_desc_bh = desc_bh;
699 	req->pr_bitmap_bh = bitmap_bh;
700 	return 0;
701 }
702 
703 /**
704  * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
705  * @inode: inode of metadata file using this allocator
706  * @req: nilfs_palloc_req structure exchanged for the removal
707  */
nilfs_palloc_abort_free_entry(struct inode * inode,struct nilfs_palloc_req * req)708 void nilfs_palloc_abort_free_entry(struct inode *inode,
709 				   struct nilfs_palloc_req *req)
710 {
711 	brelse(req->pr_bitmap_bh);
712 	brelse(req->pr_desc_bh);
713 
714 	req->pr_entry_nr = 0;
715 	req->pr_bitmap_bh = NULL;
716 	req->pr_desc_bh = NULL;
717 }
718 
719 /**
720  * nilfs_palloc_freev - deallocate a set of persistent objects
721  * @inode: inode of metadata file using this allocator
722  * @entry_nrs: array of entry numbers to be deallocated
723  * @nitems: number of entries stored in @entry_nrs
724  */
nilfs_palloc_freev(struct inode * inode,__u64 * entry_nrs,size_t nitems)725 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
726 {
727 	struct buffer_head *desc_bh, *bitmap_bh;
728 	struct nilfs_palloc_group_desc *desc;
729 	unsigned char *bitmap;
730 	void *desc_kaddr, *bitmap_kaddr;
731 	unsigned long group, group_offset;
732 	__u64 group_min_nr, last_nrs[8];
733 	const unsigned long epg = nilfs_palloc_entries_per_group(inode);
734 	const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block;
735 	unsigned int entry_start, end, pos;
736 	spinlock_t *lock;
737 	int i, j, k, ret;
738 	u32 nfree;
739 
740 	for (i = 0; i < nitems; i = j) {
741 		int change_group = false;
742 		int nempties = 0, n = 0;
743 
744 		group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
745 		ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
746 		if (ret < 0)
747 			return ret;
748 		ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
749 						    &bitmap_bh);
750 		if (ret < 0) {
751 			brelse(desc_bh);
752 			return ret;
753 		}
754 
755 		/* Get the first entry number of the group */
756 		group_min_nr = (__u64)group * epg;
757 
758 		bitmap_kaddr = kmap(bitmap_bh->b_page);
759 		bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
760 		lock = nilfs_mdt_bgl_lock(inode, group);
761 
762 		j = i;
763 		entry_start = rounddown(group_offset, epb);
764 		do {
765 			if (!nilfs_clear_bit_atomic(lock, group_offset,
766 						    bitmap)) {
767 				nilfs_msg(inode->i_sb, KERN_WARNING,
768 					  "%s (ino=%lu): entry number %llu already freed",
769 					  __func__, inode->i_ino,
770 					  (unsigned long long)entry_nrs[j]);
771 			} else {
772 				n++;
773 			}
774 
775 			j++;
776 			if (j >= nitems || entry_nrs[j] < group_min_nr ||
777 			    entry_nrs[j] >= group_min_nr + epg) {
778 				change_group = true;
779 			} else {
780 				group_offset = entry_nrs[j] - group_min_nr;
781 				if (group_offset >= entry_start &&
782 				    group_offset < entry_start + epb) {
783 					/* This entry is in the same block */
784 					continue;
785 				}
786 			}
787 
788 			/* Test if the entry block is empty or not */
789 			end = entry_start + epb;
790 			pos = nilfs_find_next_bit(bitmap, end, entry_start);
791 			if (pos >= end) {
792 				last_nrs[nempties++] = entry_nrs[j - 1];
793 				if (nempties >= ARRAY_SIZE(last_nrs))
794 					break;
795 			}
796 
797 			if (change_group)
798 				break;
799 
800 			/* Go on to the next entry block */
801 			entry_start = rounddown(group_offset, epb);
802 		} while (true);
803 
804 		kunmap(bitmap_bh->b_page);
805 		mark_buffer_dirty(bitmap_bh);
806 		brelse(bitmap_bh);
807 
808 		for (k = 0; k < nempties; k++) {
809 			ret = nilfs_palloc_delete_entry_block(inode,
810 							      last_nrs[k]);
811 			if (ret && ret != -ENOENT)
812 				nilfs_msg(inode->i_sb, KERN_WARNING,
813 					  "error %d deleting block that object (entry=%llu, ino=%lu) belongs to",
814 					  ret, (unsigned long long)last_nrs[k],
815 					  inode->i_ino);
816 		}
817 
818 		desc_kaddr = kmap_atomic(desc_bh->b_page);
819 		desc = nilfs_palloc_block_get_group_desc(
820 			inode, group, desc_bh, desc_kaddr);
821 		nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n);
822 		kunmap_atomic(desc_kaddr);
823 		mark_buffer_dirty(desc_bh);
824 		nilfs_mdt_mark_dirty(inode);
825 		brelse(desc_bh);
826 
827 		if (nfree == nilfs_palloc_entries_per_group(inode)) {
828 			ret = nilfs_palloc_delete_bitmap_block(inode, group);
829 			if (ret && ret != -ENOENT)
830 				nilfs_msg(inode->i_sb, KERN_WARNING,
831 					  "error %d deleting bitmap block of group=%lu, ino=%lu",
832 					  ret, group, inode->i_ino);
833 		}
834 	}
835 	return 0;
836 }
837 
nilfs_palloc_setup_cache(struct inode * inode,struct nilfs_palloc_cache * cache)838 void nilfs_palloc_setup_cache(struct inode *inode,
839 			      struct nilfs_palloc_cache *cache)
840 {
841 	NILFS_MDT(inode)->mi_palloc_cache = cache;
842 	spin_lock_init(&cache->lock);
843 }
844 
nilfs_palloc_clear_cache(struct inode * inode)845 void nilfs_palloc_clear_cache(struct inode *inode)
846 {
847 	struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
848 
849 	spin_lock(&cache->lock);
850 	brelse(cache->prev_desc.bh);
851 	brelse(cache->prev_bitmap.bh);
852 	brelse(cache->prev_entry.bh);
853 	cache->prev_desc.bh = NULL;
854 	cache->prev_bitmap.bh = NULL;
855 	cache->prev_entry.bh = NULL;
856 	spin_unlock(&cache->lock);
857 }
858 
nilfs_palloc_destroy_cache(struct inode * inode)859 void nilfs_palloc_destroy_cache(struct inode *inode)
860 {
861 	nilfs_palloc_clear_cache(inode);
862 	NILFS_MDT(inode)->mi_palloc_cache = NULL;
863 }
864