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