2 * alloc.c - NILFS dat/inode allocator
4 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * Originally written by Koji Sato.
17 * Two allocators were unified by Ryusuke Konishi and Amagai Yoshiji.
20 #include <linux/types.h>
21 #include <linux/buffer_head.h>
23 #include <linux/bitops.h>
24 #include <linux/slab.h>
30 * nilfs_palloc_groups_per_desc_block - get the number of groups that a group
31 * descriptor block can maintain
32 * @inode: inode of metadata file using this allocator
34 static inline unsigned long
35 nilfs_palloc_groups_per_desc_block(const struct inode
*inode
)
37 return (1UL << inode
->i_blkbits
) /
38 sizeof(struct nilfs_palloc_group_desc
);
42 * nilfs_palloc_groups_count - get maximum number of groups
43 * @inode: inode of metadata file using this allocator
45 static inline unsigned long
46 nilfs_palloc_groups_count(const struct inode
*inode
)
48 return 1UL << (BITS_PER_LONG
- (inode
->i_blkbits
+ 3 /* log2(8) */));
52 * nilfs_palloc_init_blockgroup - initialize private variables for allocator
53 * @inode: inode of metadata file using this allocator
54 * @entry_size: size of the persistent object
56 int nilfs_palloc_init_blockgroup(struct inode
*inode
, unsigned entry_size
)
58 struct nilfs_mdt_info
*mi
= NILFS_MDT(inode
);
60 mi
->mi_bgl
= kmalloc(sizeof(*mi
->mi_bgl
), GFP_NOFS
);
64 bgl_lock_init(mi
->mi_bgl
);
66 nilfs_mdt_set_entry_size(inode
, entry_size
, 0);
68 mi
->mi_blocks_per_group
=
69 DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode
),
70 mi
->mi_entries_per_block
) + 1;
71 /* Number of blocks in a group including entry blocks and
73 mi
->mi_blocks_per_desc_block
=
74 nilfs_palloc_groups_per_desc_block(inode
) *
75 mi
->mi_blocks_per_group
+ 1;
76 /* Number of blocks per descriptor including the
82 * nilfs_palloc_group - get group number and offset from an entry number
83 * @inode: inode of metadata file using this allocator
84 * @nr: serial number of the entry (e.g. inode number)
85 * @offset: pointer to store offset number in the group
87 static unsigned long nilfs_palloc_group(const struct inode
*inode
, __u64 nr
,
88 unsigned long *offset
)
92 *offset
= do_div(group
, nilfs_palloc_entries_per_group(inode
));
97 * nilfs_palloc_desc_blkoff - get block offset of a group descriptor block
98 * @inode: inode of metadata file using this allocator
99 * @group: group number
101 * nilfs_palloc_desc_blkoff() returns block offset of the descriptor
102 * block which contains a descriptor of the specified group.
105 nilfs_palloc_desc_blkoff(const struct inode
*inode
, unsigned long group
)
107 unsigned long desc_block
=
108 group
/ nilfs_palloc_groups_per_desc_block(inode
);
109 return desc_block
* NILFS_MDT(inode
)->mi_blocks_per_desc_block
;
113 * nilfs_palloc_bitmap_blkoff - get block offset of a bitmap block
114 * @inode: inode of metadata file using this allocator
115 * @group: group number
117 * nilfs_palloc_bitmap_blkoff() returns block offset of the bitmap
118 * block used to allocate/deallocate entries in the specified group.
121 nilfs_palloc_bitmap_blkoff(const struct inode
*inode
, unsigned long group
)
123 unsigned long desc_offset
=
124 group
% nilfs_palloc_groups_per_desc_block(inode
);
125 return nilfs_palloc_desc_blkoff(inode
, group
) + 1 +
126 desc_offset
* NILFS_MDT(inode
)->mi_blocks_per_group
;
130 * nilfs_palloc_group_desc_nfrees - get the number of free entries in a group
131 * @desc: pointer to descriptor structure for the group
132 * @lock: spin lock protecting @desc
135 nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc
*desc
,
141 nfree
= le32_to_cpu(desc
->pg_nfrees
);
147 * nilfs_palloc_group_desc_add_entries - adjust count of free entries
148 * @desc: pointer to descriptor structure for the group
149 * @lock: spin lock protecting @desc
150 * @n: delta to be added
153 nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc
*desc
,
154 spinlock_t
*lock
, u32 n
)
159 le32_add_cpu(&desc
->pg_nfrees
, n
);
160 nfree
= le32_to_cpu(desc
->pg_nfrees
);
166 * nilfs_palloc_entry_blkoff - get block offset of an entry block
167 * @inode: inode of metadata file using this allocator
168 * @nr: serial number of the entry (e.g. inode number)
171 nilfs_palloc_entry_blkoff(const struct inode
*inode
, __u64 nr
)
173 unsigned long group
, group_offset
;
175 group
= nilfs_palloc_group(inode
, nr
, &group_offset
);
177 return nilfs_palloc_bitmap_blkoff(inode
, group
) + 1 +
178 group_offset
/ NILFS_MDT(inode
)->mi_entries_per_block
;
182 * nilfs_palloc_desc_block_init - initialize buffer of a group descriptor block
183 * @inode: inode of metadata file
184 * @bh: buffer head of the buffer to be initialized
185 * @kaddr: kernel address mapped for the page including the buffer
187 static void nilfs_palloc_desc_block_init(struct inode
*inode
,
188 struct buffer_head
*bh
, void *kaddr
)
190 struct nilfs_palloc_group_desc
*desc
= kaddr
+ bh_offset(bh
);
191 unsigned long n
= nilfs_palloc_groups_per_desc_block(inode
);
194 nfrees
= cpu_to_le32(nilfs_palloc_entries_per_group(inode
));
196 desc
->pg_nfrees
= nfrees
;
201 static int nilfs_palloc_get_block(struct inode
*inode
, unsigned long blkoff
,
203 void (*init_block
)(struct inode
*,
204 struct buffer_head
*,
206 struct buffer_head
**bhp
,
207 struct nilfs_bh_assoc
*prev
,
213 if (prev
->bh
&& blkoff
== prev
->blkoff
) {
221 ret
= nilfs_mdt_get_block(inode
, blkoff
, create
, init_block
, bhp
);
225 * The following code must be safe for change of the
226 * cache contents during the get block call.
231 prev
->blkoff
= blkoff
;
238 * nilfs_palloc_delete_block - delete a block on the persistent allocator file
239 * @inode: inode of metadata file using this allocator
240 * @blkoff: block offset
241 * @prev: nilfs_bh_assoc struct of the last used buffer
242 * @lock: spin lock protecting @prev
244 static int nilfs_palloc_delete_block(struct inode
*inode
, unsigned long blkoff
,
245 struct nilfs_bh_assoc
*prev
,
249 if (prev
->bh
&& blkoff
== prev
->blkoff
) {
254 return nilfs_mdt_delete_block(inode
, blkoff
);
258 * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block
259 * @inode: inode of metadata file using this allocator
260 * @group: group number
261 * @create: create flag
262 * @bhp: pointer to store the resultant buffer head
264 static int nilfs_palloc_get_desc_block(struct inode
*inode
,
266 int create
, struct buffer_head
**bhp
)
268 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
270 return nilfs_palloc_get_block(inode
,
271 nilfs_palloc_desc_blkoff(inode
, group
),
272 create
, nilfs_palloc_desc_block_init
,
273 bhp
, &cache
->prev_desc
, &cache
->lock
);
277 * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block
278 * @inode: inode of metadata file using this allocator
279 * @group: group number
280 * @create: create flag
281 * @bhp: pointer to store the resultant buffer head
283 static int nilfs_palloc_get_bitmap_block(struct inode
*inode
,
285 int create
, struct buffer_head
**bhp
)
287 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
289 return nilfs_palloc_get_block(inode
,
290 nilfs_palloc_bitmap_blkoff(inode
, group
),
292 &cache
->prev_bitmap
, &cache
->lock
);
296 * nilfs_palloc_delete_bitmap_block - delete a bitmap block
297 * @inode: inode of metadata file using this allocator
298 * @group: group number
300 static int nilfs_palloc_delete_bitmap_block(struct inode
*inode
,
303 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
305 return nilfs_palloc_delete_block(inode
,
306 nilfs_palloc_bitmap_blkoff(inode
,
308 &cache
->prev_bitmap
, &cache
->lock
);
312 * nilfs_palloc_get_entry_block - get buffer head of an entry block
313 * @inode: inode of metadata file using this allocator
314 * @nr: serial number of the entry (e.g. inode number)
315 * @create: create flag
316 * @bhp: pointer to store the resultant buffer head
318 int nilfs_palloc_get_entry_block(struct inode
*inode
, __u64 nr
,
319 int create
, struct buffer_head
**bhp
)
321 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
323 return nilfs_palloc_get_block(inode
,
324 nilfs_palloc_entry_blkoff(inode
, nr
),
326 &cache
->prev_entry
, &cache
->lock
);
330 * nilfs_palloc_delete_entry_block - delete an entry block
331 * @inode: inode of metadata file using this allocator
332 * @nr: serial number of the entry
334 static int nilfs_palloc_delete_entry_block(struct inode
*inode
, __u64 nr
)
336 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
338 return nilfs_palloc_delete_block(inode
,
339 nilfs_palloc_entry_blkoff(inode
, nr
),
340 &cache
->prev_entry
, &cache
->lock
);
344 * nilfs_palloc_block_get_group_desc - get kernel address of a group descriptor
345 * @inode: inode of metadata file using this allocator
346 * @group: group number
347 * @bh: buffer head of the buffer storing the group descriptor block
348 * @kaddr: kernel address mapped for the page including the buffer
350 static struct nilfs_palloc_group_desc
*
351 nilfs_palloc_block_get_group_desc(const struct inode
*inode
,
353 const struct buffer_head
*bh
, void *kaddr
)
355 return (struct nilfs_palloc_group_desc
*)(kaddr
+ bh_offset(bh
)) +
356 group
% nilfs_palloc_groups_per_desc_block(inode
);
360 * nilfs_palloc_block_get_entry - get kernel address of an entry
361 * @inode: inode of metadata file using this allocator
362 * @nr: serial number of the entry (e.g. inode number)
363 * @bh: buffer head of the buffer storing the entry block
364 * @kaddr: kernel address mapped for the page including the buffer
366 void *nilfs_palloc_block_get_entry(const struct inode
*inode
, __u64 nr
,
367 const struct buffer_head
*bh
, void *kaddr
)
369 unsigned long entry_offset
, group_offset
;
371 nilfs_palloc_group(inode
, nr
, &group_offset
);
372 entry_offset
= group_offset
% NILFS_MDT(inode
)->mi_entries_per_block
;
374 return kaddr
+ bh_offset(bh
) +
375 entry_offset
* NILFS_MDT(inode
)->mi_entry_size
;
379 * nilfs_palloc_find_available_slot - find available slot in a group
380 * @bitmap: bitmap of the group
381 * @target: offset number of an entry in the group (start point)
382 * @bsize: size in bits
383 * @lock: spin lock protecting @bitmap
385 static int nilfs_palloc_find_available_slot(unsigned char *bitmap
,
386 unsigned long target
,
390 int pos
, end
= bsize
;
392 if (likely(target
< bsize
)) {
395 pos
= nilfs_find_next_zero_bit(bitmap
, end
, pos
);
398 if (!nilfs_set_bit_atomic(lock
, pos
, bitmap
))
400 } while (++pos
< end
);
406 for (pos
= 0; pos
< end
; pos
++) {
407 pos
= nilfs_find_next_zero_bit(bitmap
, end
, pos
);
410 if (!nilfs_set_bit_atomic(lock
, pos
, bitmap
))
418 * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups
419 * in a group descriptor block
420 * @inode: inode of metadata file using this allocator
421 * @curr: current group number
422 * @max: maximum number of groups
425 nilfs_palloc_rest_groups_in_desc_block(const struct inode
*inode
,
426 unsigned long curr
, unsigned long max
)
428 return min_t(unsigned long,
429 nilfs_palloc_groups_per_desc_block(inode
) -
430 curr
% nilfs_palloc_groups_per_desc_block(inode
),
435 * nilfs_palloc_count_desc_blocks - count descriptor blocks number
436 * @inode: inode of metadata file using this allocator
437 * @desc_blocks: descriptor blocks number [out]
439 static int nilfs_palloc_count_desc_blocks(struct inode
*inode
,
440 unsigned long *desc_blocks
)
445 ret
= nilfs_bmap_last_key(NILFS_I(inode
)->i_bmap
, &blknum
);
447 *desc_blocks
= DIV_ROUND_UP(
448 (unsigned long)blknum
,
449 NILFS_MDT(inode
)->mi_blocks_per_desc_block
);
454 * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
456 * @inode: inode of metadata file using this allocator
457 * @desc_blocks: known current descriptor blocks count
459 static inline bool nilfs_palloc_mdt_file_can_grow(struct inode
*inode
,
460 unsigned long desc_blocks
)
462 return (nilfs_palloc_groups_per_desc_block(inode
) * desc_blocks
) <
463 nilfs_palloc_groups_count(inode
);
467 * nilfs_palloc_count_max_entries - count max number of entries that can be
468 * described by descriptor blocks count
469 * @inode: inode of metadata file using this allocator
470 * @nused: current number of used entries
471 * @nmaxp: max number of entries [out]
473 int nilfs_palloc_count_max_entries(struct inode
*inode
, u64 nused
, u64
*nmaxp
)
475 unsigned long desc_blocks
= 0;
476 u64 entries_per_desc_block
, nmax
;
479 err
= nilfs_palloc_count_desc_blocks(inode
, &desc_blocks
);
483 entries_per_desc_block
= (u64
)nilfs_palloc_entries_per_group(inode
) *
484 nilfs_palloc_groups_per_desc_block(inode
);
485 nmax
= entries_per_desc_block
* desc_blocks
;
488 nilfs_palloc_mdt_file_can_grow(inode
, desc_blocks
))
489 nmax
+= entries_per_desc_block
;
499 * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
500 * @inode: inode of metadata file using this allocator
501 * @req: nilfs_palloc_req structure exchanged for the allocation
503 int nilfs_palloc_prepare_alloc_entry(struct inode
*inode
,
504 struct nilfs_palloc_req
*req
)
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
;
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
);
522 for (i
= 0; i
< ngroups
; i
+= n
) {
523 if (group
>= ngroups
) {
526 maxgroup
= nilfs_palloc_group(inode
, req
->pr_entry_nr
,
527 &maxgroup_offset
) - 1;
529 ret
= nilfs_palloc_get_desc_block(inode
, group
, 1, &desc_bh
);
532 desc_kaddr
= kmap(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
,
537 for (j
= 0; j
< n
; j
++, desc
++, group
++) {
538 lock
= nilfs_mdt_bgl_lock(inode
, group
);
539 if (nilfs_palloc_group_desc_nfrees(desc
, lock
) > 0) {
540 ret
= nilfs_palloc_get_bitmap_block(
541 inode
, group
, 1, &bitmap_bh
);
544 bitmap_kaddr
= kmap(bitmap_bh
->b_page
);
545 bitmap
= bitmap_kaddr
+ bh_offset(bitmap_bh
);
546 pos
= nilfs_palloc_find_available_slot(
547 bitmap
, group_offset
,
548 entries_per_group
, lock
);
550 /* found a free entry */
551 nilfs_palloc_group_desc_add_entries(
554 entries_per_group
* group
+ pos
;
555 kunmap(desc_bh
->b_page
);
556 kunmap(bitmap_bh
->b_page
);
558 req
->pr_desc_bh
= desc_bh
;
559 req
->pr_bitmap_bh
= bitmap_bh
;
562 kunmap(bitmap_bh
->b_page
);
569 kunmap(desc_bh
->b_page
);
573 /* no entries left */
577 kunmap(desc_bh
->b_page
);
583 * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
584 * @inode: inode of metadata file using this allocator
585 * @req: nilfs_palloc_req structure exchanged for the allocation
587 void nilfs_palloc_commit_alloc_entry(struct inode
*inode
,
588 struct nilfs_palloc_req
*req
)
590 mark_buffer_dirty(req
->pr_bitmap_bh
);
591 mark_buffer_dirty(req
->pr_desc_bh
);
592 nilfs_mdt_mark_dirty(inode
);
594 brelse(req
->pr_bitmap_bh
);
595 brelse(req
->pr_desc_bh
);
599 * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
600 * @inode: inode of metadata file using this allocator
601 * @req: nilfs_palloc_req structure exchanged for the removal
603 void nilfs_palloc_commit_free_entry(struct inode
*inode
,
604 struct nilfs_palloc_req
*req
)
606 struct nilfs_palloc_group_desc
*desc
;
607 unsigned long group
, group_offset
;
608 unsigned char *bitmap
;
609 void *desc_kaddr
, *bitmap_kaddr
;
612 group
= nilfs_palloc_group(inode
, req
->pr_entry_nr
, &group_offset
);
613 desc_kaddr
= kmap(req
->pr_desc_bh
->b_page
);
614 desc
= nilfs_palloc_block_get_group_desc(inode
, group
,
615 req
->pr_desc_bh
, desc_kaddr
);
616 bitmap_kaddr
= kmap(req
->pr_bitmap_bh
->b_page
);
617 bitmap
= bitmap_kaddr
+ bh_offset(req
->pr_bitmap_bh
);
618 lock
= nilfs_mdt_bgl_lock(inode
, group
);
620 if (!nilfs_clear_bit_atomic(lock
, group_offset
, bitmap
))
621 nilfs_warning(inode
->i_sb
, __func__
,
622 "entry number %llu already freed: ino=%lu\n",
623 (unsigned long long)req
->pr_entry_nr
,
624 (unsigned long)inode
->i_ino
);
626 nilfs_palloc_group_desc_add_entries(desc
, lock
, 1);
628 kunmap(req
->pr_bitmap_bh
->b_page
);
629 kunmap(req
->pr_desc_bh
->b_page
);
631 mark_buffer_dirty(req
->pr_desc_bh
);
632 mark_buffer_dirty(req
->pr_bitmap_bh
);
633 nilfs_mdt_mark_dirty(inode
);
635 brelse(req
->pr_bitmap_bh
);
636 brelse(req
->pr_desc_bh
);
640 * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
641 * @inode: inode of metadata file using this allocator
642 * @req: nilfs_palloc_req structure exchanged for the allocation
644 void nilfs_palloc_abort_alloc_entry(struct inode
*inode
,
645 struct nilfs_palloc_req
*req
)
647 struct nilfs_palloc_group_desc
*desc
;
648 void *desc_kaddr
, *bitmap_kaddr
;
649 unsigned char *bitmap
;
650 unsigned long group
, group_offset
;
653 group
= nilfs_palloc_group(inode
, req
->pr_entry_nr
, &group_offset
);
654 desc_kaddr
= kmap(req
->pr_desc_bh
->b_page
);
655 desc
= nilfs_palloc_block_get_group_desc(inode
, group
,
656 req
->pr_desc_bh
, desc_kaddr
);
657 bitmap_kaddr
= kmap(req
->pr_bitmap_bh
->b_page
);
658 bitmap
= bitmap_kaddr
+ bh_offset(req
->pr_bitmap_bh
);
659 lock
= nilfs_mdt_bgl_lock(inode
, group
);
661 if (!nilfs_clear_bit_atomic(lock
, group_offset
, bitmap
))
662 nilfs_warning(inode
->i_sb
, __func__
,
663 "entry number %llu already freed: ino=%lu\n",
664 (unsigned long long)req
->pr_entry_nr
,
665 (unsigned long)inode
->i_ino
);
667 nilfs_palloc_group_desc_add_entries(desc
, lock
, 1);
669 kunmap(req
->pr_bitmap_bh
->b_page
);
670 kunmap(req
->pr_desc_bh
->b_page
);
672 brelse(req
->pr_bitmap_bh
);
673 brelse(req
->pr_desc_bh
);
675 req
->pr_entry_nr
= 0;
676 req
->pr_bitmap_bh
= NULL
;
677 req
->pr_desc_bh
= NULL
;
681 * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
682 * @inode: inode of metadata file using this allocator
683 * @req: nilfs_palloc_req structure exchanged for the removal
685 int nilfs_palloc_prepare_free_entry(struct inode
*inode
,
686 struct nilfs_palloc_req
*req
)
688 struct buffer_head
*desc_bh
, *bitmap_bh
;
689 unsigned long group
, group_offset
;
692 group
= nilfs_palloc_group(inode
, req
->pr_entry_nr
, &group_offset
);
693 ret
= nilfs_palloc_get_desc_block(inode
, group
, 1, &desc_bh
);
696 ret
= nilfs_palloc_get_bitmap_block(inode
, group
, 1, &bitmap_bh
);
702 req
->pr_desc_bh
= desc_bh
;
703 req
->pr_bitmap_bh
= bitmap_bh
;
708 * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
709 * @inode: inode of metadata file using this allocator
710 * @req: nilfs_palloc_req structure exchanged for the removal
712 void nilfs_palloc_abort_free_entry(struct inode
*inode
,
713 struct nilfs_palloc_req
*req
)
715 brelse(req
->pr_bitmap_bh
);
716 brelse(req
->pr_desc_bh
);
718 req
->pr_entry_nr
= 0;
719 req
->pr_bitmap_bh
= NULL
;
720 req
->pr_desc_bh
= NULL
;
724 * nilfs_palloc_freev - deallocate a set of persistent objects
725 * @inode: inode of metadata file using this allocator
726 * @entry_nrs: array of entry numbers to be deallocated
727 * @nitems: number of entries stored in @entry_nrs
729 int nilfs_palloc_freev(struct inode
*inode
, __u64
*entry_nrs
, size_t nitems
)
731 struct buffer_head
*desc_bh
, *bitmap_bh
;
732 struct nilfs_palloc_group_desc
*desc
;
733 unsigned char *bitmap
;
734 void *desc_kaddr
, *bitmap_kaddr
;
735 unsigned long group
, group_offset
;
736 __u64 group_min_nr
, last_nrs
[8];
737 const unsigned long epg
= nilfs_palloc_entries_per_group(inode
);
738 const unsigned epb
= NILFS_MDT(inode
)->mi_entries_per_block
;
739 unsigned entry_start
, end
, pos
;
744 for (i
= 0; i
< nitems
; i
= j
) {
745 int change_group
= false;
746 int nempties
= 0, n
= 0;
748 group
= nilfs_palloc_group(inode
, entry_nrs
[i
], &group_offset
);
749 ret
= nilfs_palloc_get_desc_block(inode
, group
, 0, &desc_bh
);
752 ret
= nilfs_palloc_get_bitmap_block(inode
, group
, 0,
759 /* Get the first entry number of the group */
760 group_min_nr
= (__u64
)group
* epg
;
762 bitmap_kaddr
= kmap(bitmap_bh
->b_page
);
763 bitmap
= bitmap_kaddr
+ bh_offset(bitmap_bh
);
764 lock
= nilfs_mdt_bgl_lock(inode
, group
);
767 entry_start
= rounddown(group_offset
, epb
);
769 if (!nilfs_clear_bit_atomic(lock
, group_offset
,
771 nilfs_warning(inode
->i_sb
, __func__
,
772 "entry number %llu already freed: ino=%lu\n",
773 (unsigned long long)entry_nrs
[j
],
774 (unsigned long)inode
->i_ino
);
780 if (j
>= nitems
|| entry_nrs
[j
] < group_min_nr
||
781 entry_nrs
[j
] >= group_min_nr
+ epg
) {
784 group_offset
= entry_nrs
[j
] - group_min_nr
;
785 if (group_offset
>= entry_start
&&
786 group_offset
< entry_start
+ epb
) {
787 /* This entry is in the same block */
792 /* Test if the entry block is empty or not */
793 end
= entry_start
+ epb
;
794 pos
= nilfs_find_next_bit(bitmap
, end
, entry_start
);
796 last_nrs
[nempties
++] = entry_nrs
[j
- 1];
797 if (nempties
>= ARRAY_SIZE(last_nrs
))
804 /* Go on to the next entry block */
805 entry_start
= rounddown(group_offset
, epb
);
808 kunmap(bitmap_bh
->b_page
);
809 mark_buffer_dirty(bitmap_bh
);
812 for (k
= 0; k
< nempties
; k
++) {
813 ret
= nilfs_palloc_delete_entry_block(inode
,
815 if (ret
&& ret
!= -ENOENT
) {
816 nilfs_warning(inode
->i_sb
, __func__
,
817 "failed to delete block of entry %llu: ino=%lu, err=%d\n",
818 (unsigned long long)last_nrs
[k
],
819 (unsigned long)inode
->i_ino
, ret
);
823 desc_kaddr
= kmap_atomic(desc_bh
->b_page
);
824 desc
= nilfs_palloc_block_get_group_desc(
825 inode
, group
, desc_bh
, desc_kaddr
);
826 nfree
= nilfs_palloc_group_desc_add_entries(desc
, lock
, n
);
827 kunmap_atomic(desc_kaddr
);
828 mark_buffer_dirty(desc_bh
);
829 nilfs_mdt_mark_dirty(inode
);
832 if (nfree
== nilfs_palloc_entries_per_group(inode
)) {
833 ret
= nilfs_palloc_delete_bitmap_block(inode
, group
);
834 if (ret
&& ret
!= -ENOENT
) {
835 nilfs_warning(inode
->i_sb
, __func__
,
836 "failed to delete bitmap block of group %lu: ino=%lu, err=%d\n",
838 (unsigned long)inode
->i_ino
, ret
);
845 void nilfs_palloc_setup_cache(struct inode
*inode
,
846 struct nilfs_palloc_cache
*cache
)
848 NILFS_MDT(inode
)->mi_palloc_cache
= cache
;
849 spin_lock_init(&cache
->lock
);
852 void nilfs_palloc_clear_cache(struct inode
*inode
)
854 struct nilfs_palloc_cache
*cache
= NILFS_MDT(inode
)->mi_palloc_cache
;
856 spin_lock(&cache
->lock
);
857 brelse(cache
->prev_desc
.bh
);
858 brelse(cache
->prev_bitmap
.bh
);
859 brelse(cache
->prev_entry
.bh
);
860 cache
->prev_desc
.bh
= NULL
;
861 cache
->prev_bitmap
.bh
= NULL
;
862 cache
->prev_entry
.bh
= NULL
;
863 spin_unlock(&cache
->lock
);
866 void nilfs_palloc_destroy_cache(struct inode
*inode
)
868 nilfs_palloc_clear_cache(inode
);
869 NILFS_MDT(inode
)->mi_palloc_cache
= NULL
;