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 void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr, 180 const struct buffer_head *bh, void *kaddr) 181 { 182 unsigned long entry_offset, group_offset; 183 184 nilfs_palloc_group(inode, nr, &group_offset); 185 entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block; 186 187 return kaddr + bh_offset(bh) + 188 entry_offset * NILFS_MDT(inode)->mi_entry_size; 189 } 190 191 static int nilfs_palloc_find_available_slot(struct inode *inode, 192 unsigned long group, 193 unsigned long target, 194 unsigned char *bitmap, 195 int bsize) /* size in bits */ 196 { 197 int curr, pos, end, i; 198 199 if (target > 0) { 200 end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1); 201 if (end > bsize) 202 end = bsize; 203 pos = nilfs_find_next_zero_bit(bitmap, end, target); 204 if (pos < end && 205 !nilfs_set_bit_atomic( 206 nilfs_mdt_bgl_lock(inode, group), pos, bitmap)) 207 return pos; 208 } else 209 end = 0; 210 211 for (i = 0, curr = end; 212 i < bsize; 213 i += BITS_PER_LONG, curr += BITS_PER_LONG) { 214 /* wrap around */ 215 if (curr >= bsize) 216 curr = 0; 217 while (*((unsigned long *)bitmap + curr / BITS_PER_LONG) 218 != ~0UL) { 219 end = curr + BITS_PER_LONG; 220 if (end > bsize) 221 end = bsize; 222 pos = nilfs_find_next_zero_bit(bitmap, end, curr); 223 if ((pos < end) && 224 !nilfs_set_bit_atomic( 225 nilfs_mdt_bgl_lock(inode, group), pos, 226 bitmap)) 227 return pos; 228 } 229 } 230 return -ENOSPC; 231 } 232 233 static unsigned long 234 nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode, 235 unsigned long curr, unsigned long max) 236 { 237 return min_t(unsigned long, 238 nilfs_palloc_groups_per_desc_block(inode) - 239 curr % nilfs_palloc_groups_per_desc_block(inode), 240 max - curr + 1); 241 } 242 243 int nilfs_palloc_prepare_alloc_entry(struct inode *inode, 244 struct nilfs_palloc_req *req) 245 { 246 struct buffer_head *desc_bh, *bitmap_bh; 247 struct nilfs_palloc_group_desc *desc; 248 unsigned char *bitmap; 249 void *desc_kaddr, *bitmap_kaddr; 250 unsigned long group, maxgroup, ngroups; 251 unsigned long group_offset, maxgroup_offset; 252 unsigned long n, entries_per_group, groups_per_desc_block; 253 unsigned long i, j; 254 int pos, ret; 255 256 ngroups = nilfs_palloc_groups_count(inode); 257 maxgroup = ngroups - 1; 258 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 259 entries_per_group = nilfs_palloc_entries_per_group(inode); 260 groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode); 261 262 for (i = 0; i < ngroups; i += n) { 263 if (group >= ngroups) { 264 /* wrap around */ 265 group = 0; 266 maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr, 267 &maxgroup_offset) - 1; 268 } 269 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 270 if (ret < 0) 271 return ret; 272 desc_kaddr = kmap(desc_bh->b_page); 273 desc = nilfs_palloc_block_get_group_desc( 274 inode, group, desc_bh, desc_kaddr); 275 n = nilfs_palloc_rest_groups_in_desc_block(inode, group, 276 maxgroup); 277 for (j = 0; j < n; j++, desc++, group++) { 278 if (nilfs_palloc_group_desc_nfrees(inode, group, desc) 279 > 0) { 280 ret = nilfs_palloc_get_bitmap_block( 281 inode, group, 1, &bitmap_bh); 282 if (ret < 0) 283 goto out_desc; 284 bitmap_kaddr = kmap(bitmap_bh->b_page); 285 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 286 pos = nilfs_palloc_find_available_slot( 287 inode, group, group_offset, bitmap, 288 entries_per_group); 289 if (pos >= 0) { 290 /* found a free entry */ 291 nilfs_palloc_group_desc_add_entries( 292 inode, group, desc, -1); 293 req->pr_entry_nr = 294 entries_per_group * group + pos; 295 kunmap(desc_bh->b_page); 296 kunmap(bitmap_bh->b_page); 297 298 req->pr_desc_bh = desc_bh; 299 req->pr_bitmap_bh = bitmap_bh; 300 return 0; 301 } 302 kunmap(bitmap_bh->b_page); 303 brelse(bitmap_bh); 304 } 305 306 group_offset = 0; 307 } 308 309 kunmap(desc_bh->b_page); 310 brelse(desc_bh); 311 } 312 313 /* no entries left */ 314 return -ENOSPC; 315 316 out_desc: 317 kunmap(desc_bh->b_page); 318 brelse(desc_bh); 319 return ret; 320 } 321 322 void nilfs_palloc_commit_alloc_entry(struct inode *inode, 323 struct nilfs_palloc_req *req) 324 { 325 nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh); 326 nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh); 327 nilfs_mdt_mark_dirty(inode); 328 329 brelse(req->pr_bitmap_bh); 330 brelse(req->pr_desc_bh); 331 } 332 333 void nilfs_palloc_commit_free_entry(struct inode *inode, 334 struct nilfs_palloc_req *req) 335 { 336 struct nilfs_palloc_group_desc *desc; 337 unsigned long group, group_offset; 338 unsigned char *bitmap; 339 void *desc_kaddr, *bitmap_kaddr; 340 341 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 342 desc_kaddr = kmap(req->pr_desc_bh->b_page); 343 desc = nilfs_palloc_block_get_group_desc(inode, group, 344 req->pr_desc_bh, desc_kaddr); 345 bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page); 346 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 347 348 if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group), 349 group_offset, bitmap)) 350 printk(KERN_WARNING "%s: entry number %llu already freed\n", 351 __func__, (unsigned long long)req->pr_entry_nr); 352 353 nilfs_palloc_group_desc_add_entries(inode, group, desc, 1); 354 355 kunmap(req->pr_bitmap_bh->b_page); 356 kunmap(req->pr_desc_bh->b_page); 357 358 nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh); 359 nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh); 360 nilfs_mdt_mark_dirty(inode); 361 362 brelse(req->pr_bitmap_bh); 363 brelse(req->pr_desc_bh); 364 } 365 366 void nilfs_palloc_abort_alloc_entry(struct inode *inode, 367 struct nilfs_palloc_req *req) 368 { 369 struct nilfs_palloc_group_desc *desc; 370 void *desc_kaddr, *bitmap_kaddr; 371 unsigned char *bitmap; 372 unsigned long group, group_offset; 373 374 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 375 desc_kaddr = kmap(req->pr_desc_bh->b_page); 376 desc = nilfs_palloc_block_get_group_desc(inode, group, 377 req->pr_desc_bh, desc_kaddr); 378 bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page); 379 bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh); 380 if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group), 381 group_offset, bitmap)) 382 printk(KERN_WARNING "%s: entry numer %llu already freed\n", 383 __func__, (unsigned long long)req->pr_entry_nr); 384 385 nilfs_palloc_group_desc_add_entries(inode, group, desc, 1); 386 387 kunmap(req->pr_bitmap_bh->b_page); 388 kunmap(req->pr_desc_bh->b_page); 389 390 brelse(req->pr_bitmap_bh); 391 brelse(req->pr_desc_bh); 392 393 req->pr_entry_nr = 0; 394 req->pr_bitmap_bh = NULL; 395 req->pr_desc_bh = NULL; 396 } 397 398 int nilfs_palloc_prepare_free_entry(struct inode *inode, 399 struct nilfs_palloc_req *req) 400 { 401 struct buffer_head *desc_bh, *bitmap_bh; 402 unsigned long group, group_offset; 403 int ret; 404 405 group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset); 406 ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh); 407 if (ret < 0) 408 return ret; 409 ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh); 410 if (ret < 0) { 411 brelse(desc_bh); 412 return ret; 413 } 414 415 req->pr_desc_bh = desc_bh; 416 req->pr_bitmap_bh = bitmap_bh; 417 return 0; 418 } 419 420 void nilfs_palloc_abort_free_entry(struct inode *inode, 421 struct nilfs_palloc_req *req) 422 { 423 brelse(req->pr_bitmap_bh); 424 brelse(req->pr_desc_bh); 425 426 req->pr_entry_nr = 0; 427 req->pr_bitmap_bh = NULL; 428 req->pr_desc_bh = NULL; 429 } 430 431 static int 432 nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr) 433 { 434 __u64 first, last; 435 436 first = group * nilfs_palloc_entries_per_group(inode); 437 last = first + nilfs_palloc_entries_per_group(inode) - 1; 438 return (nr >= first) && (nr <= last); 439 } 440 441 int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems) 442 { 443 struct buffer_head *desc_bh, *bitmap_bh; 444 struct nilfs_palloc_group_desc *desc; 445 unsigned char *bitmap; 446 void *desc_kaddr, *bitmap_kaddr; 447 unsigned long group, group_offset; 448 int i, j, n, ret; 449 450 for (i = 0; i < nitems; i += n) { 451 group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset); 452 ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh); 453 if (ret < 0) 454 return ret; 455 ret = nilfs_palloc_get_bitmap_block(inode, group, 0, 456 &bitmap_bh); 457 if (ret < 0) { 458 brelse(desc_bh); 459 return ret; 460 } 461 desc_kaddr = kmap(desc_bh->b_page); 462 desc = nilfs_palloc_block_get_group_desc( 463 inode, group, desc_bh, desc_kaddr); 464 bitmap_kaddr = kmap(bitmap_bh->b_page); 465 bitmap = bitmap_kaddr + bh_offset(bitmap_bh); 466 for (j = i, n = 0; 467 (j < nitems) && nilfs_palloc_group_is_in(inode, group, 468 entry_nrs[j]); 469 j++, n++) { 470 nilfs_palloc_group(inode, entry_nrs[j], &group_offset); 471 if (!nilfs_clear_bit_atomic( 472 nilfs_mdt_bgl_lock(inode, group), 473 group_offset, bitmap)) { 474 printk(KERN_WARNING 475 "%s: entry number %llu already freed\n", 476 __func__, 477 (unsigned long long)entry_nrs[j]); 478 } 479 } 480 nilfs_palloc_group_desc_add_entries(inode, group, desc, n); 481 482 kunmap(bitmap_bh->b_page); 483 kunmap(desc_bh->b_page); 484 485 nilfs_mdt_mark_buffer_dirty(desc_bh); 486 nilfs_mdt_mark_buffer_dirty(bitmap_bh); 487 nilfs_mdt_mark_dirty(inode); 488 489 brelse(bitmap_bh); 490 brelse(desc_bh); 491 } 492 return 0; 493 } 494