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