blob: 2ccbf5531554b74612420c6bd1ff6cc8ca7d6463 [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 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 * Original code was written by Koji Sato <koji@osrg.net>.
21 * Two allocators were unified by Ryusuke Konishi <ryusuke@osrg.net>,
22 * Amagai Yoshiji <amagai@osrg.net>.
23 */
24
25#include <linux/types.h>
26#include <linux/buffer_head.h>
27#include <linux/fs.h>
28#include <linux/bitops.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090029#include <linux/slab.h>
Ryusuke Konishi54426802009-04-06 19:01:29 -070030#include "mdt.h"
31#include "alloc.h"
32
33
Ryusuke Konishidb55d922010-04-12 01:46:02 +090034/**
35 * nilfs_palloc_groups_per_desc_block - get the number of groups that a group
36 * descriptor block can maintain
37 * @inode: inode of metadata file using this allocator
38 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070039static inline unsigned long
40nilfs_palloc_groups_per_desc_block(const struct inode *inode)
41{
42 return (1UL << inode->i_blkbits) /
43 sizeof(struct nilfs_palloc_group_desc);
44}
45
Ryusuke Konishidb55d922010-04-12 01:46:02 +090046/**
47 * nilfs_palloc_groups_count - get maximum number of groups
48 * @inode: inode of metadata file using this allocator
49 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070050static inline unsigned long
51nilfs_palloc_groups_count(const struct inode *inode)
52{
53 return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
54}
55
Ryusuke Konishidb55d922010-04-12 01:46:02 +090056/**
57 * nilfs_palloc_init_blockgroup - initialize private variables for allocator
58 * @inode: inode of metadata file using this allocator
59 * @entry_size: size of the persistent object
60 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070061int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
62{
63 struct nilfs_mdt_info *mi = NILFS_MDT(inode);
64
65 mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS);
66 if (!mi->mi_bgl)
67 return -ENOMEM;
68
69 bgl_lock_init(mi->mi_bgl);
70
71 nilfs_mdt_set_entry_size(inode, entry_size, 0);
72
73 mi->mi_blocks_per_group =
74 DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode),
75 mi->mi_entries_per_block) + 1;
76 /* Number of blocks in a group including entry blocks and
77 a bitmap block */
78 mi->mi_blocks_per_desc_block =
79 nilfs_palloc_groups_per_desc_block(inode) *
80 mi->mi_blocks_per_group + 1;
81 /* Number of blocks per descriptor including the
82 descriptor block */
83 return 0;
84}
85
Ryusuke Konishidb55d922010-04-12 01:46:02 +090086/**
87 * nilfs_palloc_group - get group number and offset from an entry number
88 * @inode: inode of metadata file using this allocator
89 * @nr: serial number of the entry (e.g. inode number)
90 * @offset: pointer to store offset number in the group
91 */
Ryusuke Konishi54426802009-04-06 19:01:29 -070092static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr,
93 unsigned long *offset)
94{
95 __u64 group = nr;
96
97 *offset = do_div(group, nilfs_palloc_entries_per_group(inode));
98 return group;
99}
100
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900101/**
102 * nilfs_palloc_desc_blkoff - get block offset of a group descriptor block
103 * @inode: inode of metadata file using this allocator
104 * @group: group number
105 *
106 * nilfs_palloc_desc_blkoff() returns block offset of the descriptor
107 * block which contains a descriptor of the specified group.
108 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700109static unsigned long
110nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group)
111{
112 unsigned long desc_block =
113 group / nilfs_palloc_groups_per_desc_block(inode);
114 return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block;
115}
116
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900117/**
118 * nilfs_palloc_bitmap_blkoff - get block offset of a bitmap block
119 * @inode: inode of metadata file using this allocator
120 * @group: group number
121 *
122 * nilfs_palloc_bitmap_blkoff() returns block offset of the bitmap
123 * block used to allocate/deallocate entries in the specified group.
124 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700125static unsigned long
126nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group)
127{
128 unsigned long desc_offset =
129 group % nilfs_palloc_groups_per_desc_block(inode);
130 return nilfs_palloc_desc_blkoff(inode, group) + 1 +
131 desc_offset * NILFS_MDT(inode)->mi_blocks_per_group;
132}
133
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900134/**
135 * nilfs_palloc_group_desc_nfrees - get the number of free entries in a group
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900136 * @desc: pointer to descriptor structure for the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800137 * @lock: spin lock protecting @desc
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900138 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700139static unsigned long
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800140nilfs_palloc_group_desc_nfrees(const struct nilfs_palloc_group_desc *desc,
141 spinlock_t *lock)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700142{
143 unsigned long nfree;
144
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800145 spin_lock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700146 nfree = le32_to_cpu(desc->pg_nfrees);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800147 spin_unlock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700148 return nfree;
149}
150
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900151/**
152 * nilfs_palloc_group_desc_add_entries - adjust count of free entries
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900153 * @desc: pointer to descriptor structure for the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800154 * @lock: spin lock protecting @desc
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900155 * @n: delta to be added
156 */
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800157static u32
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800158nilfs_palloc_group_desc_add_entries(struct nilfs_palloc_group_desc *desc,
159 spinlock_t *lock, u32 n)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700160{
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800161 u32 nfree;
162
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800163 spin_lock(lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700164 le32_add_cpu(&desc->pg_nfrees, n);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800165 nfree = le32_to_cpu(desc->pg_nfrees);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800166 spin_unlock(lock);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800167 return nfree;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700168}
169
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900170/**
171 * nilfs_palloc_entry_blkoff - get block offset of an entry block
172 * @inode: inode of metadata file using this allocator
173 * @nr: serial number of the entry (e.g. inode number)
174 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700175static unsigned long
176nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr)
177{
178 unsigned long group, group_offset;
179
180 group = nilfs_palloc_group(inode, nr, &group_offset);
181
182 return nilfs_palloc_bitmap_blkoff(inode, group) + 1 +
183 group_offset / NILFS_MDT(inode)->mi_entries_per_block;
184}
185
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900186/**
187 * nilfs_palloc_desc_block_init - initialize buffer of a group descriptor block
188 * @inode: inode of metadata file
189 * @bh: buffer head of the buffer to be initialized
190 * @kaddr: kernel address mapped for the page including the buffer
191 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700192static void nilfs_palloc_desc_block_init(struct inode *inode,
193 struct buffer_head *bh, void *kaddr)
194{
195 struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh);
196 unsigned long n = nilfs_palloc_groups_per_desc_block(inode);
197 __le32 nfrees;
198
199 nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode));
200 while (n-- > 0) {
201 desc->pg_nfrees = nfrees;
202 desc++;
203 }
204}
205
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900206static int nilfs_palloc_get_block(struct inode *inode, unsigned long blkoff,
207 int create,
208 void (*init_block)(struct inode *,
209 struct buffer_head *,
210 void *),
211 struct buffer_head **bhp,
212 struct nilfs_bh_assoc *prev,
213 spinlock_t *lock)
214{
215 int ret;
216
217 spin_lock(lock);
218 if (prev->bh && blkoff == prev->blkoff) {
219 get_bh(prev->bh);
220 *bhp = prev->bh;
221 spin_unlock(lock);
222 return 0;
223 }
224 spin_unlock(lock);
225
226 ret = nilfs_mdt_get_block(inode, blkoff, create, init_block, bhp);
227 if (!ret) {
228 spin_lock(lock);
229 /*
230 * The following code must be safe for change of the
231 * cache contents during the get block call.
232 */
233 brelse(prev->bh);
234 get_bh(*bhp);
235 prev->bh = *bhp;
236 prev->blkoff = blkoff;
237 spin_unlock(lock);
238 }
239 return ret;
240}
241
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900242/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800243 * nilfs_palloc_delete_block - delete a block on the persistent allocator file
244 * @inode: inode of metadata file using this allocator
245 * @blkoff: block offset
246 * @prev: nilfs_bh_assoc struct of the last used buffer
247 * @lock: spin lock protecting @prev
248 */
249static int nilfs_palloc_delete_block(struct inode *inode, unsigned long blkoff,
250 struct nilfs_bh_assoc *prev,
251 spinlock_t *lock)
252{
253 spin_lock(lock);
254 if (prev->bh && blkoff == prev->blkoff) {
255 brelse(prev->bh);
256 prev->bh = NULL;
257 }
258 spin_unlock(lock);
259 return nilfs_mdt_delete_block(inode, blkoff);
260}
261
262/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900263 * nilfs_palloc_get_desc_block - get buffer head of a group descriptor block
264 * @inode: inode of metadata file using this allocator
265 * @group: group number
266 * @create: create flag
267 * @bhp: pointer to store the resultant buffer head
268 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700269static int nilfs_palloc_get_desc_block(struct inode *inode,
270 unsigned long group,
271 int create, struct buffer_head **bhp)
272{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900273 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
274
275 return nilfs_palloc_get_block(inode,
276 nilfs_palloc_desc_blkoff(inode, group),
277 create, nilfs_palloc_desc_block_init,
278 bhp, &cache->prev_desc, &cache->lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700279}
280
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900281/**
282 * nilfs_palloc_get_bitmap_block - get buffer head of a bitmap block
283 * @inode: inode of metadata file using this allocator
284 * @group: group number
285 * @create: create flag
286 * @bhp: pointer to store the resultant buffer head
287 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700288static int nilfs_palloc_get_bitmap_block(struct inode *inode,
289 unsigned long group,
290 int create, struct buffer_head **bhp)
291{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900292 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
293
294 return nilfs_palloc_get_block(inode,
295 nilfs_palloc_bitmap_blkoff(inode, group),
296 create, NULL, bhp,
297 &cache->prev_bitmap, &cache->lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700298}
299
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900300/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800301 * nilfs_palloc_delete_bitmap_block - delete a bitmap block
302 * @inode: inode of metadata file using this allocator
303 * @group: group number
304 */
305static int nilfs_palloc_delete_bitmap_block(struct inode *inode,
306 unsigned long group)
307{
308 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
309
310 return nilfs_palloc_delete_block(inode,
311 nilfs_palloc_bitmap_blkoff(inode,
312 group),
313 &cache->prev_bitmap, &cache->lock);
314}
315
316/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900317 * nilfs_palloc_get_entry_block - get buffer head of an entry block
318 * @inode: inode of metadata file using this allocator
319 * @nr: serial number of the entry (e.g. inode number)
320 * @create: create flag
321 * @bhp: pointer to store the resultant buffer head
322 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700323int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
324 int create, struct buffer_head **bhp)
325{
Ryusuke Konishi70622a22009-11-14 18:40:27 +0900326 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
327
328 return nilfs_palloc_get_block(inode,
329 nilfs_palloc_entry_blkoff(inode, nr),
330 create, NULL, bhp,
331 &cache->prev_entry, &cache->lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700332}
333
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900334/**
Ryusuke Konishida019952015-11-06 16:31:54 -0800335 * nilfs_palloc_delete_entry_block - delete an entry block
336 * @inode: inode of metadata file using this allocator
337 * @nr: serial number of the entry
338 */
339static int nilfs_palloc_delete_entry_block(struct inode *inode, __u64 nr)
340{
341 struct nilfs_palloc_cache *cache = NILFS_MDT(inode)->mi_palloc_cache;
342
343 return nilfs_palloc_delete_block(inode,
344 nilfs_palloc_entry_blkoff(inode, nr),
345 &cache->prev_entry, &cache->lock);
346}
347
348/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900349 * nilfs_palloc_block_get_group_desc - get kernel address of a group descriptor
350 * @inode: inode of metadata file using this allocator
351 * @group: group number
352 * @bh: buffer head of the buffer storing the group descriptor block
353 * @kaddr: kernel address mapped for the page including the buffer
354 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700355static struct nilfs_palloc_group_desc *
356nilfs_palloc_block_get_group_desc(const struct inode *inode,
357 unsigned long group,
358 const struct buffer_head *bh, void *kaddr)
359{
360 return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
361 group % nilfs_palloc_groups_per_desc_block(inode);
362}
363
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900364/**
365 * nilfs_palloc_block_get_entry - get kernel address of an entry
366 * @inode: inode of metadata file using this allocator
367 * @nr: serial number of the entry (e.g. inode number)
368 * @bh: buffer head of the buffer storing the entry block
369 * @kaddr: kernel address mapped for the page including the buffer
370 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700371void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
372 const struct buffer_head *bh, void *kaddr)
373{
374 unsigned long entry_offset, group_offset;
375
376 nilfs_palloc_group(inode, nr, &group_offset);
377 entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
378
379 return kaddr + bh_offset(bh) +
380 entry_offset * NILFS_MDT(inode)->mi_entry_size;
381}
382
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900383/**
384 * nilfs_palloc_find_available_slot - find available slot in a group
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900385 * @bitmap: bitmap of the group
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800386 * @target: offset number of an entry in the group (start point)
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900387 * @bsize: size in bits
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800388 * @lock: spin lock protecting @bitmap
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900389 */
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800390static int nilfs_palloc_find_available_slot(unsigned char *bitmap,
Ryusuke Konishi54426802009-04-06 19:01:29 -0700391 unsigned long target,
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800392 unsigned bsize,
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800393 spinlock_t *lock)
Ryusuke Konishi54426802009-04-06 19:01:29 -0700394{
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800395 int pos, end = bsize;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700396
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800397 if (likely(target < bsize)) {
398 pos = target;
399 do {
400 pos = nilfs_find_next_zero_bit(bitmap, end, pos);
401 if (pos >= end)
402 break;
403 if (!nilfs_set_bit_atomic(lock, pos, bitmap))
Ryusuke Konishi54426802009-04-06 19:01:29 -0700404 return pos;
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800405 } while (++pos < end);
406
407 end = target;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700408 }
Ryusuke Konishi18c41b32015-11-06 16:31:48 -0800409
410 /* wrap around */
411 for (pos = 0; pos < end; pos++) {
412 pos = nilfs_find_next_zero_bit(bitmap, end, pos);
413 if (pos >= end)
414 break;
415 if (!nilfs_set_bit_atomic(lock, pos, bitmap))
416 return pos;
417 }
418
Ryusuke Konishi54426802009-04-06 19:01:29 -0700419 return -ENOSPC;
420}
421
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900422/**
423 * nilfs_palloc_rest_groups_in_desc_block - get the remaining number of groups
424 * in a group descriptor block
425 * @inode: inode of metadata file using this allocator
426 * @curr: current group number
427 * @max: maximum number of groups
428 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700429static unsigned long
430nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
431 unsigned long curr, unsigned long max)
432{
433 return min_t(unsigned long,
434 nilfs_palloc_groups_per_desc_block(inode) -
435 curr % nilfs_palloc_groups_per_desc_block(inode),
436 max - curr + 1);
437}
438
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900439/**
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700440 * nilfs_palloc_count_desc_blocks - count descriptor blocks number
441 * @inode: inode of metadata file using this allocator
442 * @desc_blocks: descriptor blocks number [out]
443 */
444static int nilfs_palloc_count_desc_blocks(struct inode *inode,
445 unsigned long *desc_blocks)
446{
Ryusuke Konishi3568a132015-04-16 12:46:34 -0700447 __u64 blknum;
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700448 int ret;
449
450 ret = nilfs_bmap_last_key(NILFS_I(inode)->i_bmap, &blknum);
451 if (likely(!ret))
452 *desc_blocks = DIV_ROUND_UP(
Ryusuke Konishi3568a132015-04-16 12:46:34 -0700453 (unsigned long)blknum,
454 NILFS_MDT(inode)->mi_blocks_per_desc_block);
Vyacheslav Dubeykoc7ef9722013-07-03 15:08:05 -0700455 return ret;
456}
457
458/**
459 * nilfs_palloc_mdt_file_can_grow - check potential opportunity for
460 * MDT file growing
461 * @inode: inode of metadata file using this allocator
462 * @desc_blocks: known current descriptor blocks count
463 */
464static inline bool nilfs_palloc_mdt_file_can_grow(struct inode *inode,
465 unsigned long desc_blocks)
466{
467 return (nilfs_palloc_groups_per_desc_block(inode) * desc_blocks) <
468 nilfs_palloc_groups_count(inode);
469}
470
471/**
472 * nilfs_palloc_count_max_entries - count max number of entries that can be
473 * described by descriptor blocks count
474 * @inode: inode of metadata file using this allocator
475 * @nused: current number of used entries
476 * @nmaxp: max number of entries [out]
477 */
478int nilfs_palloc_count_max_entries(struct inode *inode, u64 nused, u64 *nmaxp)
479{
480 unsigned long desc_blocks = 0;
481 u64 entries_per_desc_block, nmax;
482 int err;
483
484 err = nilfs_palloc_count_desc_blocks(inode, &desc_blocks);
485 if (unlikely(err))
486 return err;
487
488 entries_per_desc_block = (u64)nilfs_palloc_entries_per_group(inode) *
489 nilfs_palloc_groups_per_desc_block(inode);
490 nmax = entries_per_desc_block * desc_blocks;
491
492 if (nused == nmax &&
493 nilfs_palloc_mdt_file_can_grow(inode, desc_blocks))
494 nmax += entries_per_desc_block;
495
496 if (nused > nmax)
497 return -ERANGE;
498
499 *nmaxp = nmax;
500 return 0;
501}
502
503/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900504 * nilfs_palloc_prepare_alloc_entry - prepare to allocate a persistent object
505 * @inode: inode of metadata file using this allocator
506 * @req: nilfs_palloc_req structure exchanged for the allocation
507 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700508int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
509 struct nilfs_palloc_req *req)
510{
511 struct buffer_head *desc_bh, *bitmap_bh;
512 struct nilfs_palloc_group_desc *desc;
513 unsigned char *bitmap;
514 void *desc_kaddr, *bitmap_kaddr;
515 unsigned long group, maxgroup, ngroups;
516 unsigned long group_offset, maxgroup_offset;
Ryusuke Konishi09ef29e2015-11-06 16:32:14 -0800517 unsigned long n, entries_per_group;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700518 unsigned long i, j;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800519 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700520 int pos, ret;
521
522 ngroups = nilfs_palloc_groups_count(inode);
523 maxgroup = ngroups - 1;
524 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
525 entries_per_group = nilfs_palloc_entries_per_group(inode);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700526
527 for (i = 0; i < ngroups; i += n) {
528 if (group >= ngroups) {
529 /* wrap around */
530 group = 0;
531 maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
532 &maxgroup_offset) - 1;
533 }
534 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
535 if (ret < 0)
536 return ret;
537 desc_kaddr = kmap(desc_bh->b_page);
538 desc = nilfs_palloc_block_get_group_desc(
539 inode, group, desc_bh, desc_kaddr);
540 n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
541 maxgroup);
542 for (j = 0; j < n; j++, desc++, group++) {
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800543 lock = nilfs_mdt_bgl_lock(inode, group);
544 if (nilfs_palloc_group_desc_nfrees(desc, lock) > 0) {
Ryusuke Konishi54426802009-04-06 19:01:29 -0700545 ret = nilfs_palloc_get_bitmap_block(
546 inode, group, 1, &bitmap_bh);
547 if (ret < 0)
548 goto out_desc;
549 bitmap_kaddr = kmap(bitmap_bh->b_page);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900550 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700551 pos = nilfs_palloc_find_available_slot(
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800552 bitmap, group_offset,
553 entries_per_group, lock);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700554 if (pos >= 0) {
555 /* found a free entry */
556 nilfs_palloc_group_desc_add_entries(
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800557 desc, lock, -1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700558 req->pr_entry_nr =
559 entries_per_group * group + pos;
560 kunmap(desc_bh->b_page);
561 kunmap(bitmap_bh->b_page);
562
563 req->pr_desc_bh = desc_bh;
564 req->pr_bitmap_bh = bitmap_bh;
565 return 0;
566 }
567 kunmap(bitmap_bh->b_page);
568 brelse(bitmap_bh);
569 }
570
571 group_offset = 0;
572 }
573
574 kunmap(desc_bh->b_page);
575 brelse(desc_bh);
576 }
577
578 /* no entries left */
579 return -ENOSPC;
580
581 out_desc:
582 kunmap(desc_bh->b_page);
583 brelse(desc_bh);
584 return ret;
585}
586
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900587/**
588 * nilfs_palloc_commit_alloc_entry - finish allocation of a persistent object
589 * @inode: inode of metadata file using this allocator
590 * @req: nilfs_palloc_req structure exchanged for the allocation
591 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700592void nilfs_palloc_commit_alloc_entry(struct inode *inode,
593 struct nilfs_palloc_req *req)
594{
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900595 mark_buffer_dirty(req->pr_bitmap_bh);
596 mark_buffer_dirty(req->pr_desc_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700597 nilfs_mdt_mark_dirty(inode);
598
599 brelse(req->pr_bitmap_bh);
600 brelse(req->pr_desc_bh);
601}
602
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900603/**
604 * nilfs_palloc_commit_free_entry - finish deallocating a persistent object
605 * @inode: inode of metadata file using this allocator
606 * @req: nilfs_palloc_req structure exchanged for the removal
607 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700608void nilfs_palloc_commit_free_entry(struct inode *inode,
609 struct nilfs_palloc_req *req)
610{
611 struct nilfs_palloc_group_desc *desc;
612 unsigned long group, group_offset;
613 unsigned char *bitmap;
614 void *desc_kaddr, *bitmap_kaddr;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800615 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700616
617 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
618 desc_kaddr = kmap(req->pr_desc_bh->b_page);
619 desc = nilfs_palloc_block_get_group_desc(inode, group,
620 req->pr_desc_bh, desc_kaddr);
621 bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900622 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800623 lock = nilfs_mdt_bgl_lock(inode, group);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700624
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800625 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
Ryusuke Konishib7bed712015-11-06 16:31:43 -0800626 nilfs_warning(inode->i_sb, __func__,
627 "entry number %llu already freed: ino=%lu\n",
628 (unsigned long long)req->pr_entry_nr,
629 (unsigned long)inode->i_ino);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900630 else
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800631 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700632
633 kunmap(req->pr_bitmap_bh->b_page);
634 kunmap(req->pr_desc_bh->b_page);
635
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900636 mark_buffer_dirty(req->pr_desc_bh);
637 mark_buffer_dirty(req->pr_bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700638 nilfs_mdt_mark_dirty(inode);
639
640 brelse(req->pr_bitmap_bh);
641 brelse(req->pr_desc_bh);
642}
643
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900644/**
645 * nilfs_palloc_abort_alloc_entry - cancel allocation of a persistent object
646 * @inode: inode of metadata file using this allocator
647 * @req: nilfs_palloc_req structure exchanged for the allocation
648 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700649void nilfs_palloc_abort_alloc_entry(struct inode *inode,
650 struct nilfs_palloc_req *req)
651{
652 struct nilfs_palloc_group_desc *desc;
653 void *desc_kaddr, *bitmap_kaddr;
654 unsigned char *bitmap;
655 unsigned long group, group_offset;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800656 spinlock_t *lock;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700657
658 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
659 desc_kaddr = kmap(req->pr_desc_bh->b_page);
660 desc = nilfs_palloc_block_get_group_desc(inode, group,
661 req->pr_desc_bh, desc_kaddr);
662 bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900663 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800664 lock = nilfs_mdt_bgl_lock(inode, group);
665
666 if (!nilfs_clear_bit_atomic(lock, group_offset, bitmap))
Ryusuke Konishib7bed712015-11-06 16:31:43 -0800667 nilfs_warning(inode->i_sb, __func__,
668 "entry number %llu already freed: ino=%lu\n",
669 (unsigned long long)req->pr_entry_nr,
670 (unsigned long)inode->i_ino);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900671 else
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800672 nilfs_palloc_group_desc_add_entries(desc, lock, 1);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700673
674 kunmap(req->pr_bitmap_bh->b_page);
675 kunmap(req->pr_desc_bh->b_page);
676
677 brelse(req->pr_bitmap_bh);
678 brelse(req->pr_desc_bh);
679
680 req->pr_entry_nr = 0;
681 req->pr_bitmap_bh = NULL;
682 req->pr_desc_bh = NULL;
683}
684
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900685/**
686 * nilfs_palloc_prepare_free_entry - prepare to deallocate a persistent object
687 * @inode: inode of metadata file using this allocator
688 * @req: nilfs_palloc_req structure exchanged for the removal
689 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700690int nilfs_palloc_prepare_free_entry(struct inode *inode,
691 struct nilfs_palloc_req *req)
692{
693 struct buffer_head *desc_bh, *bitmap_bh;
694 unsigned long group, group_offset;
695 int ret;
696
697 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
698 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
699 if (ret < 0)
700 return ret;
701 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
702 if (ret < 0) {
703 brelse(desc_bh);
704 return ret;
705 }
706
707 req->pr_desc_bh = desc_bh;
708 req->pr_bitmap_bh = bitmap_bh;
709 return 0;
710}
711
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900712/**
713 * nilfs_palloc_abort_free_entry - cancel deallocating a persistent object
714 * @inode: inode of metadata file using this allocator
715 * @req: nilfs_palloc_req structure exchanged for the removal
716 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700717void nilfs_palloc_abort_free_entry(struct inode *inode,
718 struct nilfs_palloc_req *req)
719{
720 brelse(req->pr_bitmap_bh);
721 brelse(req->pr_desc_bh);
722
723 req->pr_entry_nr = 0;
724 req->pr_bitmap_bh = NULL;
725 req->pr_desc_bh = NULL;
726}
727
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900728/**
Ryusuke Konishidb55d922010-04-12 01:46:02 +0900729 * nilfs_palloc_freev - deallocate a set of persistent objects
730 * @inode: inode of metadata file using this allocator
731 * @entry_nrs: array of entry numbers to be deallocated
732 * @nitems: number of entries stored in @entry_nrs
733 */
Ryusuke Konishi54426802009-04-06 19:01:29 -0700734int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
735{
736 struct buffer_head *desc_bh, *bitmap_bh;
737 struct nilfs_palloc_group_desc *desc;
738 unsigned char *bitmap;
739 void *desc_kaddr, *bitmap_kaddr;
740 unsigned long group, group_offset;
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800741 __u64 group_min_nr, last_nrs[8];
Ryusuke Konishib2258092015-11-06 16:31:51 -0800742 const unsigned long epg = nilfs_palloc_entries_per_group(inode);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800743 const unsigned epb = NILFS_MDT(inode)->mi_entries_per_block;
744 unsigned entry_start, end, pos;
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800745 spinlock_t *lock;
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800746 int i, j, k, ret;
747 u32 nfree;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700748
Ryusuke Konishi349dbc32011-05-10 20:59:34 +0900749 for (i = 0; i < nitems; i = j) {
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800750 int change_group = false;
751 int nempties = 0, n = 0;
752
Ryusuke Konishi54426802009-04-06 19:01:29 -0700753 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
754 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
755 if (ret < 0)
756 return ret;
757 ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
758 &bitmap_bh);
759 if (ret < 0) {
760 brelse(desc_bh);
761 return ret;
762 }
Ryusuke Konishib2258092015-11-06 16:31:51 -0800763
764 /* Get the first entry number of the group */
765 group_min_nr = (__u64)group * epg;
766
Ryusuke Konishi54426802009-04-06 19:01:29 -0700767 bitmap_kaddr = kmap(bitmap_bh->b_page);
Ryusuke Konishi141bbdb2009-11-14 13:48:06 +0900768 bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800769 lock = nilfs_mdt_bgl_lock(inode, group);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800770
771 j = i;
772 entry_start = rounddown(group_offset, epb);
773 do {
Ryusuke Konishi4e9e63a2015-11-06 16:31:45 -0800774 if (!nilfs_clear_bit_atomic(lock, group_offset,
775 bitmap)) {
Ryusuke Konishib7bed712015-11-06 16:31:43 -0800776 nilfs_warning(inode->i_sb, __func__,
777 "entry number %llu already freed: ino=%lu\n",
778 (unsigned long long)entry_nrs[j],
779 (unsigned long)inode->i_ino);
Ryusuke Konishi9954e7a2011-02-23 02:26:17 +0900780 } else {
781 n++;
Ryusuke Konishi54426802009-04-06 19:01:29 -0700782 }
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800783
784 j++;
785 if (j >= nitems || entry_nrs[j] < group_min_nr ||
786 entry_nrs[j] >= group_min_nr + epg) {
787 change_group = true;
788 } else {
789 group_offset = entry_nrs[j] - group_min_nr;
790 if (group_offset >= entry_start &&
791 group_offset < entry_start + epb) {
792 /* This entry is in the same block */
793 continue;
794 }
795 }
796
797 /* Test if the entry block is empty or not */
798 end = entry_start + epb;
799 pos = nilfs_find_next_bit(bitmap, end, entry_start);
800 if (pos >= end) {
801 last_nrs[nempties++] = entry_nrs[j - 1];
802 if (nempties >= ARRAY_SIZE(last_nrs))
803 break;
804 }
805
806 if (change_group)
807 break;
808
809 /* Go on to the next entry block */
810 entry_start = rounddown(group_offset, epb);
811 } while (true);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700812
813 kunmap(bitmap_bh->b_page);
Ryusuke Konishi5fc7b142011-05-05 12:56:51 +0900814 mark_buffer_dirty(bitmap_bh);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700815 brelse(bitmap_bh);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800816
817 for (k = 0; k < nempties; k++) {
818 ret = nilfs_palloc_delete_entry_block(inode,
819 last_nrs[k]);
820 if (ret && ret != -ENOENT) {
821 nilfs_warning(inode->i_sb, __func__,
822 "failed to delete block of entry %llu: ino=%lu, err=%d\n",
823 (unsigned long long)last_nrs[k],
824 (unsigned long)inode->i_ino, ret);
825 }
826 }
827
828 desc_kaddr = kmap_atomic(desc_bh->b_page);
829 desc = nilfs_palloc_block_get_group_desc(
830 inode, group, desc_bh, desc_kaddr);
831 nfree = nilfs_palloc_group_desc_add_entries(desc, lock, n);
832 kunmap_atomic(desc_kaddr);
833 mark_buffer_dirty(desc_bh);
834 nilfs_mdt_mark_dirty(inode);
Ryusuke Konishi54426802009-04-06 19:01:29 -0700835 brelse(desc_bh);
Ryusuke Konishid0c14a92015-11-06 16:31:56 -0800836
837 if (nfree == nilfs_palloc_entries_per_group(inode)) {
838 ret = nilfs_palloc_delete_bitmap_block(inode, group);
839 if (ret && ret != -ENOENT) {
840 nilfs_warning(inode->i_sb, __func__,
841 "failed to delete bitmap block of group %lu: ino=%lu, err=%d\n",
842 group,
843 (unsigned long)inode->i_ino, ret);
844 }
845 }
Ryusuke Konishi54426802009-04-06 19:01:29 -0700846 }
847 return 0;
848}
Ryusuke Konishidb38d5a2009-11-14 15:54:27 +0900849
850void 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
857void 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
871void nilfs_palloc_destroy_cache(struct inode *inode)
872{
873 nilfs_palloc_clear_cache(inode);
874 NILFS_MDT(inode)->mi_palloc_cache = NULL;
875}