alloc.c

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