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