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