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