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 | * | |
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> | |
29 | #include "mdt.h" | |
30 | #include "alloc.h" | |
31 | ||
32 | ||
33 | static inline unsigned long | |
34 | nilfs_palloc_groups_per_desc_block(const struct inode *inode) | |
35 | { | |
36 | return (1UL << inode->i_blkbits) / | |
37 | sizeof(struct nilfs_palloc_group_desc); | |
38 | } | |
39 | ||
40 | static inline unsigned long | |
41 | nilfs_palloc_groups_count(const struct inode *inode) | |
42 | { | |
43 | return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */)); | |
44 | } | |
45 | ||
46 | int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size) | |
47 | { | |
48 | struct nilfs_mdt_info *mi = NILFS_MDT(inode); | |
49 | ||
50 | mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS); | |
51 | if (!mi->mi_bgl) | |
52 | return -ENOMEM; | |
53 | ||
54 | bgl_lock_init(mi->mi_bgl); | |
55 | ||
56 | nilfs_mdt_set_entry_size(inode, entry_size, 0); | |
57 | ||
58 | mi->mi_blocks_per_group = | |
59 | DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode), | |
60 | mi->mi_entries_per_block) + 1; | |
61 | /* Number of blocks in a group including entry blocks and | |
62 | a bitmap block */ | |
63 | mi->mi_blocks_per_desc_block = | |
64 | nilfs_palloc_groups_per_desc_block(inode) * | |
65 | mi->mi_blocks_per_group + 1; | |
66 | /* Number of blocks per descriptor including the | |
67 | descriptor block */ | |
68 | return 0; | |
69 | } | |
70 | ||
71 | static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr, | |
72 | unsigned long *offset) | |
73 | { | |
74 | __u64 group = nr; | |
75 | ||
76 | *offset = do_div(group, nilfs_palloc_entries_per_group(inode)); | |
77 | return group; | |
78 | } | |
79 | ||
80 | static unsigned long | |
81 | nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group) | |
82 | { | |
83 | unsigned long desc_block = | |
84 | group / nilfs_palloc_groups_per_desc_block(inode); | |
85 | return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block; | |
86 | } | |
87 | ||
88 | static unsigned long | |
89 | nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group) | |
90 | { | |
91 | unsigned long desc_offset = | |
92 | group % nilfs_palloc_groups_per_desc_block(inode); | |
93 | return nilfs_palloc_desc_blkoff(inode, group) + 1 + | |
94 | desc_offset * NILFS_MDT(inode)->mi_blocks_per_group; | |
95 | } | |
96 | ||
97 | static unsigned long | |
98 | nilfs_palloc_group_desc_nfrees(struct inode *inode, unsigned long group, | |
99 | const struct nilfs_palloc_group_desc *desc) | |
100 | { | |
101 | unsigned long nfree; | |
102 | ||
103 | spin_lock(nilfs_mdt_bgl_lock(inode, group)); | |
104 | nfree = le32_to_cpu(desc->pg_nfrees); | |
105 | spin_unlock(nilfs_mdt_bgl_lock(inode, group)); | |
106 | return nfree; | |
107 | } | |
108 | ||
109 | static void | |
110 | nilfs_palloc_group_desc_add_entries(struct inode *inode, | |
111 | unsigned long group, | |
112 | struct nilfs_palloc_group_desc *desc, | |
113 | u32 n) | |
114 | { | |
115 | spin_lock(nilfs_mdt_bgl_lock(inode, group)); | |
116 | le32_add_cpu(&desc->pg_nfrees, n); | |
117 | spin_unlock(nilfs_mdt_bgl_lock(inode, group)); | |
118 | } | |
119 | ||
120 | static unsigned long | |
121 | nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr) | |
122 | { | |
123 | unsigned long group, group_offset; | |
124 | ||
125 | group = nilfs_palloc_group(inode, nr, &group_offset); | |
126 | ||
127 | return nilfs_palloc_bitmap_blkoff(inode, group) + 1 + | |
128 | group_offset / NILFS_MDT(inode)->mi_entries_per_block; | |
129 | } | |
130 | ||
131 | static void nilfs_palloc_desc_block_init(struct inode *inode, | |
132 | struct buffer_head *bh, void *kaddr) | |
133 | { | |
134 | struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh); | |
135 | unsigned long n = nilfs_palloc_groups_per_desc_block(inode); | |
136 | __le32 nfrees; | |
137 | ||
138 | nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode)); | |
139 | while (n-- > 0) { | |
140 | desc->pg_nfrees = nfrees; | |
141 | desc++; | |
142 | } | |
143 | } | |
144 | ||
145 | static int nilfs_palloc_get_desc_block(struct inode *inode, | |
146 | unsigned long group, | |
147 | int create, struct buffer_head **bhp) | |
148 | { | |
149 | return nilfs_mdt_get_block(inode, | |
150 | nilfs_palloc_desc_blkoff(inode, group), | |
151 | create, nilfs_palloc_desc_block_init, bhp); | |
152 | } | |
153 | ||
154 | static int nilfs_palloc_get_bitmap_block(struct inode *inode, | |
155 | unsigned long group, | |
156 | int create, struct buffer_head **bhp) | |
157 | { | |
158 | return nilfs_mdt_get_block(inode, | |
159 | nilfs_palloc_bitmap_blkoff(inode, group), | |
160 | create, NULL, bhp); | |
161 | } | |
162 | ||
163 | int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr, | |
164 | int create, struct buffer_head **bhp) | |
165 | { | |
166 | return nilfs_mdt_get_block(inode, nilfs_palloc_entry_blkoff(inode, nr), | |
167 | create, NULL, bhp); | |
168 | } | |
169 | ||
170 | static struct nilfs_palloc_group_desc * | |
171 | nilfs_palloc_block_get_group_desc(const struct inode *inode, | |
172 | unsigned long group, | |
173 | const struct buffer_head *bh, void *kaddr) | |
174 | { | |
175 | return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) + | |
176 | group % nilfs_palloc_groups_per_desc_block(inode); | |
177 | } | |
178 | ||
179 | static unsigned char * | |
180 | nilfs_palloc_block_get_bitmap(const struct inode *inode, | |
181 | const struct buffer_head *bh, void *kaddr) | |
182 | { | |
183 | return (unsigned char *)(kaddr + bh_offset(bh)); | |
184 | } | |
185 | ||
186 | void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr, | |
187 | const struct buffer_head *bh, void *kaddr) | |
188 | { | |
189 | unsigned long entry_offset, group_offset; | |
190 | ||
191 | nilfs_palloc_group(inode, nr, &group_offset); | |
192 | entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block; | |
193 | ||
194 | return kaddr + bh_offset(bh) + | |
195 | entry_offset * NILFS_MDT(inode)->mi_entry_size; | |
196 | } | |
197 | ||
198 | static int nilfs_palloc_find_available_slot(struct inode *inode, | |
199 | unsigned long group, | |
200 | unsigned long target, | |
201 | unsigned char *bitmap, | |
202 | int bsize) /* size in bits */ | |
203 | { | |
204 | int curr, pos, end, i; | |
205 | ||
206 | if (target > 0) { | |
207 | end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1); | |
208 | if (end > bsize) | |
209 | end = bsize; | |
210 | pos = nilfs_find_next_zero_bit(bitmap, end, target); | |
211 | if (pos < end && | |
212 | !nilfs_set_bit_atomic( | |
213 | nilfs_mdt_bgl_lock(inode, group), pos, bitmap)) | |
214 | return pos; | |
215 | } else | |
216 | end = 0; | |
217 | ||
218 | for (i = 0, curr = end; | |
219 | i < bsize; | |
220 | i += BITS_PER_LONG, curr += BITS_PER_LONG) { | |
221 | /* wrap around */ | |
222 | if (curr >= bsize) | |
223 | curr = 0; | |
224 | while (*((unsigned long *)bitmap + curr / BITS_PER_LONG) | |
225 | != ~0UL) { | |
226 | end = curr + BITS_PER_LONG; | |
227 | if (end > bsize) | |
228 | end = bsize; | |
229 | pos = nilfs_find_next_zero_bit(bitmap, end, curr); | |
230 | if ((pos < end) && | |
231 | !nilfs_set_bit_atomic( | |
232 | nilfs_mdt_bgl_lock(inode, group), pos, | |
233 | bitmap)) | |
234 | return pos; | |
235 | } | |
236 | } | |
237 | return -ENOSPC; | |
238 | } | |
239 | ||
240 | static unsigned long | |
241 | nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode, | |
242 | unsigned long curr, unsigned long max) | |
243 | { | |
244 | return min_t(unsigned long, | |
245 | nilfs_palloc_groups_per_desc_block(inode) - | |
246 | curr % nilfs_palloc_groups_per_desc_block(inode), | |
247 | max - curr + 1); | |
248 | } | |
249 | ||
250 | int nilfs_palloc_prepare_alloc_entry(struct inode *inode, | |
251 | struct nilfs_palloc_req *req) | |
252 | { | |
253 | struct buffer_head *desc_bh, *bitmap_bh; | |
254 | struct nilfs_palloc_group_desc *desc; | |
255 | unsigned char *bitmap; | |
256 | void *desc_kaddr, *bitmap_kaddr; | |
257 | unsigned long group, maxgroup, ngroups; | |
258 | unsigned long group_offset, maxgroup_offset; | |
259 | unsigned long n, entries_per_group, groups_per_desc_block; | |
260 | unsigned long i, j; | |
261 | int pos, ret; | |
262 | ||
263 | ngroups = nilfs_palloc_groups_count(inode); | |
264 | maxgroup = ngroups - 1; | |
265 | group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); | |
266 | entries_per_group = nilfs_palloc_entries_per_group(inode); | |
267 | groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode); | |
268 | ||
269 | for (i = 0; i < ngroups; i += n) { | |
270 | if (group >= ngroups) { | |
271 | /* wrap around */ | |
272 | group = 0; | |
273 | maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr, | |
274 | &maxgroup_offset) - 1; | |
275 | } | |
276 | ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); | |
277 | if (ret < 0) | |
278 | return ret; | |
279 | desc_kaddr = kmap(desc_bh->b_page); | |
280 | desc = nilfs_palloc_block_get_group_desc( | |
281 | inode, group, desc_bh, desc_kaddr); | |
282 | n = nilfs_palloc_rest_groups_in_desc_block(inode, group, | |
283 | maxgroup); | |
284 | for (j = 0; j < n; j++, desc++, group++) { | |
285 | if (nilfs_palloc_group_desc_nfrees(inode, group, desc) | |
286 | > 0) { | |
287 | ret = nilfs_palloc_get_bitmap_block( | |
288 | inode, group, 1, &bitmap_bh); | |
289 | if (ret < 0) | |
290 | goto out_desc; | |
291 | bitmap_kaddr = kmap(bitmap_bh->b_page); | |
292 | bitmap = nilfs_palloc_block_get_bitmap( | |
293 | inode, bitmap_bh, bitmap_kaddr); | |
294 | pos = nilfs_palloc_find_available_slot( | |
295 | inode, group, group_offset, bitmap, | |
296 | entries_per_group); | |
297 | if (pos >= 0) { | |
298 | /* found a free entry */ | |
299 | nilfs_palloc_group_desc_add_entries( | |
300 | inode, group, desc, -1); | |
301 | req->pr_entry_nr = | |
302 | entries_per_group * group + pos; | |
303 | kunmap(desc_bh->b_page); | |
304 | kunmap(bitmap_bh->b_page); | |
305 | ||
306 | req->pr_desc_bh = desc_bh; | |
307 | req->pr_bitmap_bh = bitmap_bh; | |
308 | return 0; | |
309 | } | |
310 | kunmap(bitmap_bh->b_page); | |
311 | brelse(bitmap_bh); | |
312 | } | |
313 | ||
314 | group_offset = 0; | |
315 | } | |
316 | ||
317 | kunmap(desc_bh->b_page); | |
318 | brelse(desc_bh); | |
319 | } | |
320 | ||
321 | /* no entries left */ | |
322 | return -ENOSPC; | |
323 | ||
324 | out_desc: | |
325 | kunmap(desc_bh->b_page); | |
326 | brelse(desc_bh); | |
327 | return ret; | |
328 | } | |
329 | ||
330 | void nilfs_palloc_commit_alloc_entry(struct inode *inode, | |
331 | struct nilfs_palloc_req *req) | |
332 | { | |
333 | nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh); | |
334 | nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh); | |
335 | nilfs_mdt_mark_dirty(inode); | |
336 | ||
337 | brelse(req->pr_bitmap_bh); | |
338 | brelse(req->pr_desc_bh); | |
339 | } | |
340 | ||
341 | void nilfs_palloc_commit_free_entry(struct inode *inode, | |
342 | struct nilfs_palloc_req *req) | |
343 | { | |
344 | struct nilfs_palloc_group_desc *desc; | |
345 | unsigned long group, group_offset; | |
346 | unsigned char *bitmap; | |
347 | void *desc_kaddr, *bitmap_kaddr; | |
348 | ||
349 | group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); | |
350 | desc_kaddr = kmap(req->pr_desc_bh->b_page); | |
351 | desc = nilfs_palloc_block_get_group_desc(inode, group, | |
352 | req->pr_desc_bh, desc_kaddr); | |
353 | bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page); | |
354 | bitmap = nilfs_palloc_block_get_bitmap(inode, req->pr_bitmap_bh, | |
355 | bitmap_kaddr); | |
356 | ||
357 | if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group), | |
358 | group_offset, bitmap)) | |
359 | printk(KERN_WARNING "%s: entry number %llu already freed\n", | |
360 | __func__, (unsigned long long)req->pr_entry_nr); | |
361 | ||
362 | nilfs_palloc_group_desc_add_entries(inode, group, desc, 1); | |
363 | ||
364 | kunmap(req->pr_bitmap_bh->b_page); | |
365 | kunmap(req->pr_desc_bh->b_page); | |
366 | ||
367 | nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh); | |
368 | nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh); | |
369 | nilfs_mdt_mark_dirty(inode); | |
370 | ||
371 | brelse(req->pr_bitmap_bh); | |
372 | brelse(req->pr_desc_bh); | |
373 | } | |
374 | ||
375 | void nilfs_palloc_abort_alloc_entry(struct inode *inode, | |
376 | struct nilfs_palloc_req *req) | |
377 | { | |
378 | struct nilfs_palloc_group_desc *desc; | |
379 | void *desc_kaddr, *bitmap_kaddr; | |
380 | unsigned char *bitmap; | |
381 | unsigned long group, group_offset; | |
382 | ||
383 | group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); | |
384 | desc_kaddr = kmap(req->pr_desc_bh->b_page); | |
385 | desc = nilfs_palloc_block_get_group_desc(inode, group, | |
386 | req->pr_desc_bh, desc_kaddr); | |
387 | bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page); | |
388 | bitmap = nilfs_palloc_block_get_bitmap(inode, req->pr_bitmap_bh, | |
389 | bitmap_kaddr); | |
390 | if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group), | |
391 | group_offset, bitmap)) | |
392 | printk(KERN_WARNING "%s: entry numer %llu already freed\n", | |
393 | __func__, (unsigned long long)req->pr_entry_nr); | |
394 | ||
395 | nilfs_palloc_group_desc_add_entries(inode, group, desc, 1); | |
396 | ||
397 | kunmap(req->pr_bitmap_bh->b_page); | |
398 | kunmap(req->pr_desc_bh->b_page); | |
399 | ||
400 | brelse(req->pr_bitmap_bh); | |
401 | brelse(req->pr_desc_bh); | |
402 | ||
403 | req->pr_entry_nr = 0; | |
404 | req->pr_bitmap_bh = NULL; | |
405 | req->pr_desc_bh = NULL; | |
406 | } | |
407 | ||
408 | int nilfs_palloc_prepare_free_entry(struct inode *inode, | |
409 | struct nilfs_palloc_req *req) | |
410 | { | |
411 | struct buffer_head *desc_bh, *bitmap_bh; | |
412 | unsigned long group, group_offset; | |
413 | int ret; | |
414 | ||
415 | group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); | |
416 | ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); | |
417 | if (ret < 0) | |
418 | return ret; | |
419 | ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh); | |
420 | if (ret < 0) { | |
421 | brelse(desc_bh); | |
422 | return ret; | |
423 | } | |
424 | ||
425 | req->pr_desc_bh = desc_bh; | |
426 | req->pr_bitmap_bh = bitmap_bh; | |
427 | return 0; | |
428 | } | |
429 | ||
430 | void nilfs_palloc_abort_free_entry(struct inode *inode, | |
431 | struct nilfs_palloc_req *req) | |
432 | { | |
433 | brelse(req->pr_bitmap_bh); | |
434 | brelse(req->pr_desc_bh); | |
435 | ||
436 | req->pr_entry_nr = 0; | |
437 | req->pr_bitmap_bh = NULL; | |
438 | req->pr_desc_bh = NULL; | |
439 | } | |
440 | ||
441 | static int | |
442 | nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr) | |
443 | { | |
444 | __u64 first, last; | |
445 | ||
446 | first = group * nilfs_palloc_entries_per_group(inode); | |
447 | last = first + nilfs_palloc_entries_per_group(inode) - 1; | |
448 | return (nr >= first) && (nr <= last); | |
449 | } | |
450 | ||
451 | int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems) | |
452 | { | |
453 | struct buffer_head *desc_bh, *bitmap_bh; | |
454 | struct nilfs_palloc_group_desc *desc; | |
455 | unsigned char *bitmap; | |
456 | void *desc_kaddr, *bitmap_kaddr; | |
457 | unsigned long group, group_offset; | |
458 | int i, j, n, ret; | |
459 | ||
460 | for (i = 0; i < nitems; i += n) { | |
461 | group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset); | |
462 | ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh); | |
463 | if (ret < 0) | |
464 | return ret; | |
465 | ret = nilfs_palloc_get_bitmap_block(inode, group, 0, | |
466 | &bitmap_bh); | |
467 | if (ret < 0) { | |
468 | brelse(desc_bh); | |
469 | return ret; | |
470 | } | |
471 | desc_kaddr = kmap(desc_bh->b_page); | |
472 | desc = nilfs_palloc_block_get_group_desc( | |
473 | inode, group, desc_bh, desc_kaddr); | |
474 | bitmap_kaddr = kmap(bitmap_bh->b_page); | |
475 | bitmap = nilfs_palloc_block_get_bitmap( | |
476 | inode, bitmap_bh, bitmap_kaddr); | |
477 | for (j = i, n = 0; | |
478 | (j < nitems) && nilfs_palloc_group_is_in(inode, group, | |
479 | entry_nrs[j]); | |
480 | j++, n++) { | |
481 | nilfs_palloc_group(inode, entry_nrs[j], &group_offset); | |
482 | if (!nilfs_clear_bit_atomic( | |
483 | nilfs_mdt_bgl_lock(inode, group), | |
484 | group_offset, bitmap)) { | |
485 | printk(KERN_WARNING | |
486 | "%s: entry number %llu already freed\n", | |
487 | __func__, | |
488 | (unsigned long long)entry_nrs[j]); | |
489 | } | |
490 | } | |
491 | nilfs_palloc_group_desc_add_entries(inode, group, desc, n); | |
492 | ||
493 | kunmap(bitmap_bh->b_page); | |
494 | kunmap(desc_bh->b_page); | |
495 | ||
496 | nilfs_mdt_mark_buffer_dirty(desc_bh); | |
497 | nilfs_mdt_mark_buffer_dirty(bitmap_bh); | |
498 | nilfs_mdt_mark_dirty(inode); | |
499 | ||
500 | brelse(bitmap_bh); | |
501 | brelse(desc_bh); | |
502 | } | |
503 | return 0; | |
504 | } |