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