blob: 2c90e285d7c6725089641bc2a3fcb336b35d054b [file] [log] [blame]
Ryusuke Konishi54426802009-04-06 19:01:29 -07001/*
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 *
Ryusuke Konishi4b420ab2016-05-23 16:23:09 -070016 * Originally written by Koji Sato.
17 * Two allocators were unified by Ryusuke Konishi and Amagai Yoshiji.
Ryusuke Konishi54426802009-04-06 19:01:29 -070018 */
19
20#include <linux/types.h>
21#include <linux/buffer_head.h>
22#include <linux/fs.h>
23#include <linux/bitops.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090024#include <linux/slab.h>
Ryusuke Konishi54426802009-04-06 19:01:29 -070025#include "mdt.h"
26#include "alloc.h"
27
28
Ryusuke Konishidb55d922010-04-12 01:46:02 +090029/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070034static inline unsigned long
35nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +090041/**
42 * nilfs_palloc_groups_count - get maximum number of groups
43 * @inode: inode of metadata file using this allocator
44 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070045static inline unsigned long
46nilfs_palloc_groups_count(const struct inode *inode)
47{
48 return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
49}
50
Ryusuke Konishidb55d922010-04-12 01:46:02 +090051/**
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 */
Ryusuke Konishi0c6c44c2016-05-23 16:23:39 -070056int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned int entry_size)
Ryusuke Konishi54426802009-04-06 19:01:29 -070057{
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;
Ryusuke Konishi076a3782016-05-23 16:23:48 -070071 /*
72 * Number of blocks in a group including entry blocks
73 * and a bitmap block
74 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070075 mi->mi_blocks_per_desc_block =
76 nilfs_palloc_groups_per_desc_block(inode) *
77 mi->mi_blocks_per_group + 1;
Ryusuke Konishi076a3782016-05-23 16:23:48 -070078 /*
79 * Number of blocks per descriptor including the
80 * descriptor block
81 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070082 return 0;
83}
84
Ryusuke Konishidb55d922010-04-12 01:46:02 +090085/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070091static 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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900100/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700108static unsigned long
109nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900116/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700124static unsigned long
125nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900133/**
134 * nilfs_palloc_group_desc_nfrees - get the number of free entries in a group
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900135 * @desc: pointer to descriptor structure for the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800136 * @lock: spin lock protecting @desc
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900137 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700138static unsigned long
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800139nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc *desc,
140 spinlock_t *lock)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700141{
142 unsigned long nfree;
143
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800144 spin_lock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700145 nfree = le32_to_cpu(desc->pg_nfrees);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800146 spin_unlock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700147 return nfree;
148}
149
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900150/**
151 * nilfs_palloc_group_desc_add_entries - adjust count of free entries
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900152 * @desc: pointer to descriptor structure for the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800153 * @lock: spin lock protecting @desc
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900154 * @n: delta to be added
155 */
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800156static u32
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800157nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc *desc,
158 spinlock_t *lock, u32 n)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700159{
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800160 u32 nfree;
161
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800162 spin_lock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700163 le32_add_cpu(&desc->pg_nfrees, n);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800164 nfree = le32_to_cpu(desc->pg_nfrees);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800165 spin_unlock(lock);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800166 return nfree;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700167}
168
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900169/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700174static unsigned long
175nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900185/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700191static 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
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900205static 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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900241/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800242 * 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 */
248static 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/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900262 * 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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700268static int nilfs_palloc_get_desc_block(struct inode *inode,
269 unsigned long group,
270 int create, struct buffer_head **bhp)
271{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900272 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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700278}
279
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900280/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700287static int nilfs_palloc_get_bitmap_block(struct inode *inode,
288 unsigned long group,
289 int create, struct buffer_head **bhp)
290{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900291 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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700297}
298
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900299/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800300 * nilfs_palloc_delete_bitmap_block - delete a bitmap block
301 * @inode: inode of metadata file using this allocator
302 * @group: group number
303 */
304static 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/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900316 * 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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700322int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
323 int create, struct buffer_head **bhp)
324{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900325 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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700331}
332
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900333/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800334 * 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 */
338static 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/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900348 * 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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700354static struct nilfs_palloc_group_desc *
355nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900363/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700370void *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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900382/**
383 * nilfs_palloc_find_available_slot - find available slot in a group
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900384 * @bitmap: bitmap of the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800385 * @target: offset number of an entry in the group (start point)
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900386 * @bsize: size in bits
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800387 * @lock: spin lock protecting @bitmap
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900388 */
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800389static int nilfs_palloc_find_available_slot(unsigned char *bitmap,
Ryusuke Konishi54426802009-04-06 19:01:29 -0700390 unsigned long target,
Ryusuke Konishi0c6c44c2016-05-23 16:23:39 -0700391 unsigned int bsize,
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800392 spinlock_t *lock)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700393{
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800394 int pos, end = bsize;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700395
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800396 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))
Ryusuke Konishi54426802009-04-06 19:01:29 -0700403 return pos;
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800404 } while (++pos < end);
405
406 end = target;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700407 }
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800408
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
Ryusuke Konishi54426802009-04-06 19:01:29 -0700418 return -ENOSPC;
419}
420
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900421/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700428static unsigned long
429nilfs_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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900438/**
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700439 * 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 */
443static int nilfs_palloc_count_desc_blocks(struct inode *inode,
444 unsigned long *desc_blocks)
445{
Ryusuke Konishi3568a132015-04-16 12:46:34 -0700446 __u64 blknum;
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700447 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(
Ryusuke Konishi3568a132015-04-16 12:46:34 -0700452 (unsigned long)blknum,
453 NILFS_MDT(inode)->mi_blocks_per_desc_block);
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700454 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 */
463static 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 */
477int 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/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900503 * 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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700507int 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;
Ryusuke Konishi09ef29e2015-11-06 16:32:14 -0800516 unsigned long n, entries_per_group;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700517 unsigned long i, j;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800518 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700519 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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700525
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++) {
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800542 lock = nilfs_mdt_bgl_lock(inode, group);
543 if (nilfs_palloc_group_desc_nfrees(desc, lock) > 0) {
Ryusuke Konishi54426802009-04-06 19:01:29 -0700544 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);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900549 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700550 pos = nilfs_palloc_find_available_slot(
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800551 bitmap, group_offset,
552 entries_per_group, lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700553 if (pos >= 0) {
554 /* found a free entry */
555 nilfs_palloc_group_desc_add_entries(
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800556 desc, lock, -1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700557 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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900586/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700591void nilfs_palloc_commit_alloc_entry(struct inode *inode,
592 struct nilfs_palloc_req *req)
593{
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900594 mark_buffer_dirty(req->pr_bitmap_bh);
595 mark_buffer_dirty(req->pr_desc_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700596 nilfs_mdt_mark_dirty(inode);
597
598 brelse(req->pr_bitmap_bh);
599 brelse(req->pr_desc_bh);
600}
601
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900602/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700607void 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;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800614 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700615
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);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900621 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800622 lock = nilfs_mdt_bgl_lock(inode, group);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700623
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800624 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
Ryusuke Konishid6517de2016-08-02 14:05:14 -0700625 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);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900629 else
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800630 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700631
632 kunmap(req->pr_bitmap_bh->b_page);
633 kunmap(req->pr_desc_bh->b_page);
634
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900635 mark_buffer_dirty(req->pr_desc_bh);
636 mark_buffer_dirty(req->pr_bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700637 nilfs_mdt_mark_dirty(inode);
638
639 brelse(req->pr_bitmap_bh);
640 brelse(req->pr_desc_bh);
641}
642
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900643/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700648void 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;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800655 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700656
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);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900662 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800663 lock = nilfs_mdt_bgl_lock(inode, group);
664
665 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
Ryusuke Konishid6517de2016-08-02 14:05:14 -0700666 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);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900670 else
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800671 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700672
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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900684/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700689int 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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900711/**
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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700716void 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
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900727/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900728 * 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 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700733int 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;
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800740 __u64 group_min_nr, last_nrs[8];
Ryusuke Konishib2258092015-11-06 16:31:51 -0800741 const unsigned long epg = nilfs_palloc_entries_per_group(inode);
Ryusuke Konishi0c6c44c2016-05-23 16:23:39 -0700742 const unsigned int epb = NILFS_MDT(inode)->mi_entries_per_block;
743 unsigned int entry_start, end, pos;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800744 spinlock_t *lock;
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800745 int i, j, k, ret;
746 u32 nfree;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700747
Ryusuke Konishi349dbc32011-05-10 20:59:34 +0900748 for (i = 0; i < nitems; i = j) {
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800749 int change_group = false;
750 int nempties = 0, n = 0;
751
Ryusuke Konishi54426802009-04-06 19:01:29 -0700752 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 }
Ryusuke Konishib2258092015-11-06 16:31:51 -0800762
763 /* Get the first entry number of the group */
764 group_min_nr = (__u64)group * epg;
765
Ryusuke Konishi54426802009-04-06 19:01:29 -0700766 bitmap_kaddr = kmap(bitmap_bh->b_page);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900767 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800768 lock = nilfs_mdt_bgl_lock(inode, group);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800769
770 j = i;
771 entry_start = rounddown(group_offset, epb);
772 do {
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800773 if (!nilfs_clear_bit_atomic(lock, group_offset,
774 bitmap)) {
Ryusuke Konishid6517de2016-08-02 14:05:14 -0700775 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]);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900779 } else {
780 n++;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700781 }
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800782
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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700811
812 kunmap(bitmap_bh->b_page);
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900813 mark_buffer_dirty(bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700814 brelse(bitmap_bh);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800815
816 for (k = 0; k < nempties; k++) {
817 ret = nilfs_palloc_delete_entry_block(inode,
818 last_nrs[k]);
Ryusuke Konishid6517de2016-08-02 14:05:14 -0700819 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);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800824 }
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);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700833 brelse(desc_bh);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800834
835 if (nfree == nilfs_palloc_entries_per_group(inode)) {
836 ret = nilfs_palloc_delete_bitmap_block(inode, group);
Ryusuke Konishid6517de2016-08-02 14:05:14 -0700837 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);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800841 }
Ryusuke Konishi54426802009-04-06 19:01:29 -0700842 }
843 return 0;
844}
Ryusuke Konishidb38d5a2009-11-14 15:54:27 +0900845
846void 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
853void 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
867void nilfs_palloc_destroy_cache(struct inode *inode)
868{
869 nilfs_palloc_clear_cache(inode);
870 NILFS_MDT(inode)->mi_palloc_cache = NULL;
871}