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 } 505