quotaio_tree.c revision d1154eb460efe588eaed3d439c1caaca149fa362
1/* 2 * Implementation of new quotafile format 3 * 4 * Jan Kara <jack@suse.cz> - sponsored by SuSE CR 5 */ 6 7#include "config.h" 8#include <sys/types.h> 9#include <errno.h> 10#include <stdio.h> 11#include <stdlib.h> 12#include <string.h> 13#include <unistd.h> 14#include <asm/byteorder.h> 15 16#include "common.h" 17#include "quotaio_tree.h" 18#include "quotaio.h" 19 20typedef char *dqbuf_t; 21 22#define getdqbuf() smalloc(QT_BLKSIZE) 23#define freedqbuf(buf) free(buf) 24 25/* Is given dquot empty? */ 26int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk) 27{ 28 int i; 29 30 for (i = 0; i < info->dqi_entry_size; i++) 31 if (disk[i]) 32 return 0; 33 return 1; 34} 35 36int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info) 37{ 38 return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) / 39 info->dqi_entry_size; 40} 41 42static int get_index(qid_t id, int depth) 43{ 44 return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff; 45} 46 47/* Read given block */ 48static void read_blk(struct quota_handle *h, uint blk, dqbuf_t buf) 49{ 50 int err; 51 52 err = h->e2fs_read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, 53 QT_BLKSIZE); 54 if (err < 0) 55 log_fatal(2, "Cannot read block %u: %s", blk, strerror(errno)); 56 else if (err != QT_BLKSIZE) 57 memset(buf + err, 0, QT_BLKSIZE - err); 58} 59 60/* Write block */ 61static int write_blk(struct quota_handle *h, uint blk, dqbuf_t buf) 62{ 63 int err; 64 65 err = h->e2fs_write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf, 66 QT_BLKSIZE); 67 if (err < 0 && errno != ENOSPC) 68 log_fatal(2, "Cannot write block (%u): %s", 69 blk, strerror(errno)); 70 if (err != QT_BLKSIZE) 71 return -ENOSPC; 72 return 0; 73} 74 75/* Get free block in file (either from free list or create new one) */ 76static int get_free_dqblk(struct quota_handle *h) 77{ 78 dqbuf_t buf = getdqbuf(); 79 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 80 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 81 int blk; 82 83 if (info->dqi_free_blk) { 84 blk = info->dqi_free_blk; 85 read_blk(h, blk, buf); 86 info->dqi_free_blk = __le32_to_cpu(dh->dqdh_next_free); 87 } else { 88 memset(buf, 0, QT_BLKSIZE); 89 /* Assure block allocation... */ 90 if (write_blk(h, info->dqi_blocks, buf) < 0) { 91 freedqbuf(buf); 92 log_err("Cannot allocate new quota block " 93 "(out of disk space).", ""); 94 return -ENOSPC; 95 } 96 blk = info->dqi_blocks++; 97 } 98 mark_quotafile_info_dirty(h); 99 freedqbuf(buf); 100 return blk; 101} 102 103/* Put given block to free list */ 104static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf, uint blk) 105{ 106 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 107 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 108 109 dh->dqdh_next_free = __cpu_to_le32(info->dqi_free_blk); 110 dh->dqdh_prev_free = __cpu_to_le32(0); 111 dh->dqdh_entries = __cpu_to_le16(0); 112 info->dqi_free_blk = blk; 113 mark_quotafile_info_dirty(h); 114 write_blk(h, blk, buf); 115} 116 117/* Remove given block from the list of blocks with free entries */ 118static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf, uint blk) 119{ 120 dqbuf_t tmpbuf = getdqbuf(); 121 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 122 uint nextblk = __le32_to_cpu(dh->dqdh_next_free), prevblk = 123 124 __le32_to_cpu(dh->dqdh_prev_free); 125 126 if (nextblk) { 127 read_blk(h, nextblk, tmpbuf); 128 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 129 dh->dqdh_prev_free; 130 write_blk(h, nextblk, tmpbuf); 131 } 132 if (prevblk) { 133 read_blk(h, prevblk, tmpbuf); 134 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free = 135 dh->dqdh_next_free; 136 write_blk(h, prevblk, tmpbuf); 137 } else { 138 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk; 139 mark_quotafile_info_dirty(h); 140 } 141 freedqbuf(tmpbuf); 142 dh->dqdh_next_free = dh->dqdh_prev_free = __cpu_to_le32(0); 143 write_blk(h, blk, buf); /* No matter whether write succeeds 144 * block is out of list */ 145} 146 147/* Insert given block to the beginning of list with free entries */ 148static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf, uint blk) 149{ 150 dqbuf_t tmpbuf = getdqbuf(); 151 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf; 152 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 153 154 dh->dqdh_next_free = __cpu_to_le32(info->dqi_free_entry); 155 dh->dqdh_prev_free = __cpu_to_le32(0); 156 write_blk(h, blk, buf); 157 if (info->dqi_free_entry) { 158 read_blk(h, info->dqi_free_entry, tmpbuf); 159 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free = 160 __cpu_to_le32(blk); 161 write_blk(h, info->dqi_free_entry, tmpbuf); 162 } 163 freedqbuf(tmpbuf); 164 info->dqi_free_entry = blk; 165 mark_quotafile_info_dirty(h); 166} 167 168/* Find space for dquot */ 169static uint find_free_dqentry(struct quota_handle *h, struct dquot *dquot, 170 int *err) 171{ 172 int blk, i; 173 struct qt_disk_dqdbheader *dh; 174 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 175 char *ddquot; 176 dqbuf_t buf; 177 178 *err = 0; 179 buf = getdqbuf(); 180 dh = (struct qt_disk_dqdbheader *)buf; 181 if (info->dqi_free_entry) { 182 blk = info->dqi_free_entry; 183 read_blk(h, blk, buf); 184 } else { 185 blk = get_free_dqblk(h); 186 if (blk < 0) { 187 freedqbuf(buf); 188 *err = blk; 189 return 0; 190 } 191 memset(buf, 0, QT_BLKSIZE); 192 info->dqi_free_entry = blk; 193 mark_quotafile_info_dirty(h); 194 } 195 196 /* Block will be full? */ 197 if (__le16_to_cpu(dh->dqdh_entries) + 1 >= qtree_dqstr_in_blk(info)) 198 remove_free_dqentry(h, buf, blk); 199 200 dh->dqdh_entries = __cpu_to_le16(__le16_to_cpu(dh->dqdh_entries) + 1); 201 /* Find free structure in block */ 202 ddquot = buf + sizeof(struct qt_disk_dqdbheader); 203 for (i = 0; 204 i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot); 205 i++) 206 ddquot += info->dqi_entry_size; 207 208 if (i == qtree_dqstr_in_blk(info)) 209 log_fatal(2, "find_free_dqentry(): Data block full but it " 210 "shouldn't.", ""); 211 212 write_blk(h, blk, buf); 213 dquot->dq_dqb.u.v2_mdqb.dqb_off = 214 (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + 215 i * info->dqi_entry_size; 216 freedqbuf(buf); 217 return blk; 218} 219 220/* Insert reference to structure into the trie */ 221static int do_insert_tree(struct quota_handle *h, struct dquot *dquot, 222 uint * treeblk, int depth) 223{ 224 dqbuf_t buf; 225 int newson = 0, newact = 0; 226 u_int32_t *ref; 227 uint newblk; 228 int ret = 0; 229 230 log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth); 231 buf = getdqbuf(); 232 if (!*treeblk) { 233 ret = get_free_dqblk(h); 234 if (ret < 0) 235 goto out_buf; 236 *treeblk = ret; 237 memset(buf, 0, QT_BLKSIZE); 238 newact = 1; 239 } else { 240 read_blk(h, *treeblk, buf); 241 } 242 243 ref = (u_int32_t *) buf; 244 newblk = __le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 245 if (!newblk) 246 newson = 1; 247 if (depth == QT_TREEDEPTH - 1) { 248 if (newblk) 249 log_fatal(2, "Inserting already present quota entry " 250 "(block %u).", 251 ref[get_index(dquot->dq_id, depth)]); 252 newblk = find_free_dqentry(h, dquot, &ret); 253 } else { 254 ret = do_insert_tree(h, dquot, &newblk, depth + 1); 255 } 256 257 if (newson && ret >= 0) { 258 ref[get_index(dquot->dq_id, depth)] = __cpu_to_le32(newblk); 259 write_blk(h, *treeblk, buf); 260 } else if (newact && ret < 0) { 261 put_free_dqblk(h, buf, *treeblk); 262 } 263 264out_buf: 265 freedqbuf(buf); 266 return ret; 267} 268 269/* Wrapper for inserting quota structure into tree */ 270static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot) 271{ 272 uint tmp = QT_TREEOFF; 273 274 if (do_insert_tree(h, dquot, &tmp, 0) < 0) 275 log_fatal(2, "Cannot write quota (id %u): %s", 276 (uint) dquot->dq_id, strerror(errno)); 277} 278 279/* Write dquot to file */ 280void qtree_write_dquot(struct dquot *dquot) 281{ 282 ssize_t ret; 283 struct quota_handle *h = dquot->dq_h; 284 struct qtree_mem_dqinfo *info = 285 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; 286 log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u", 287 dquot->dq_dqb.u.v2_mdqb.dqb_off, 288 info->dqi_entry_size); 289 char *ddquot = (char *)smalloc(info->dqi_entry_size); 290 291 if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) 292 dq_insert_tree(dquot->dq_h, dquot); 293 info->dqi_ops->mem2disk_dqblk(ddquot, dquot); 294 log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u", 295 dquot->dq_dqb.u.v2_mdqb.dqb_off, 296 info->dqi_entry_size); 297 ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot, 298 info->dqi_entry_size); 299 300 if (ret != info->dqi_entry_size) { 301 if (ret > 0) 302 errno = ENOSPC; 303 log_fatal(2, "Quota write failed (id %u): %s", 304 (uint)dquot->dq_id, strerror(errno)); 305 } 306} 307 308/* Free dquot entry in data block */ 309static void free_dqentry(struct quota_handle *h, struct dquot *dquot, uint blk) 310{ 311 struct qt_disk_dqdbheader *dh; 312 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 313 dqbuf_t buf = getdqbuf(); 314 315 if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk) 316 log_fatal(2, "Quota structure has offset to other block (%u) " 317 "than it should (%u).", blk, 318 (uint) (dquot->dq_dqb.u.v2_mdqb.dqb_off >> 319 QT_BLKSIZE_BITS)); 320 321 read_blk(h, blk, buf); 322 dh = (struct qt_disk_dqdbheader *)buf; 323 dh->dqdh_entries = __cpu_to_le16(__le16_to_cpu(dh->dqdh_entries) - 1); 324 325 if (!__le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */ 326 remove_free_dqentry(h, buf, blk); 327 put_free_dqblk(h, buf, blk); 328 } else { 329 memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off & 330 ((1 << QT_BLKSIZE_BITS) - 1)), 331 0, info->dqi_entry_size); 332 333 /* First free entry? */ 334 if (__le16_to_cpu(dh->dqdh_entries) == 335 qtree_dqstr_in_blk(info) - 1) 336 /* This will also write data block */ 337 insert_free_dqentry(h, buf, blk); 338 else 339 write_blk(h, blk, buf); 340 } 341 dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; 342 freedqbuf(buf); 343} 344 345/* Remove reference to dquot from tree */ 346static void remove_tree(struct quota_handle *h, struct dquot *dquot, 347 uint * blk, int depth) 348{ 349 dqbuf_t buf = getdqbuf(); 350 uint newblk; 351 u_int32_t *ref = (u_int32_t *) buf; 352 353 read_blk(h, *blk, buf); 354 newblk = __le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 355 if (depth == QT_TREEDEPTH - 1) { 356 free_dqentry(h, dquot, newblk); 357 newblk = 0; 358 } else { 359 remove_tree(h, dquot, &newblk, depth + 1); 360 } 361 362 if (!newblk) { 363 int i; 364 365 ref[get_index(dquot->dq_id, depth)] = __cpu_to_le32(0); 366 367 /* Block got empty? */ 368 for (i = 0; i < QT_BLKSIZE && !buf[i]; i++); 369 370 /* Don't put the root block into the free block list */ 371 if (i == QT_BLKSIZE && *blk != QT_TREEOFF) { 372 put_free_dqblk(h, buf, *blk); 373 *blk = 0; 374 } else { 375 write_blk(h, *blk, buf); 376 } 377 } 378 freedqbuf(buf); 379} 380 381/* Delete dquot from tree */ 382void qtree_delete_dquot(struct dquot *dquot) 383{ 384 uint tmp = QT_TREEOFF; 385 386 if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) /* Even not allocated? */ 387 return; 388 remove_tree(dquot->dq_h, dquot, &tmp, 0); 389} 390 391/* Find entry in block */ 392static loff_t find_block_dqentry(struct quota_handle *h, 393 struct dquot *dquot, uint blk) 394{ 395 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 396 dqbuf_t buf = getdqbuf(); 397 int i; 398 char *ddquot = buf + sizeof(struct qt_disk_dqdbheader); 399 400 read_blk(h, blk, buf); 401 for (i = 0; 402 i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot); 403 i++) 404 ddquot += info->dqi_entry_size; 405 406 if (i == qtree_dqstr_in_blk(info)) 407 log_fatal(2, "Quota for id %u referenced but not present.", 408 dquot->dq_id); 409 freedqbuf(buf); 410 return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) + 411 i * info->dqi_entry_size; 412} 413 414/* Find entry for given id in the tree */ 415static loff_t find_tree_dqentry(struct quota_handle *h, struct dquot *dquot, 416 uint blk, int depth) 417{ 418 dqbuf_t buf = getdqbuf(); 419 loff_t ret = 0; 420 u_int32_t *ref = (u_int32_t *) buf; 421 422 read_blk(h, blk, buf); 423 ret = 0; 424 blk = __le32_to_cpu(ref[get_index(dquot->dq_id, depth)]); 425 if (!blk) /* No reference? */ 426 goto out_buf; 427 if (depth < QT_TREEDEPTH - 1) 428 ret = find_tree_dqentry(h, dquot, blk, depth + 1); 429 else 430 ret = find_block_dqentry(h, dquot, blk); 431out_buf: 432 freedqbuf(buf); 433 return ret; 434} 435 436/* Find entry for given id in the tree - wrapper function */ 437static inline loff_t find_dqentry(struct quota_handle *h, struct dquot *dquot) 438{ 439 return find_tree_dqentry(h, dquot, QT_TREEOFF, 0); 440} 441 442/* 443 * Read dquot (either from disk or from kernel) 444 * User can use errno to detect errstr when NULL is returned 445 */ 446struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id) 447{ 448 struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree; 449 loff_t offset; 450 ssize_t ret; 451 char *ddquot = smalloc(info->dqi_entry_size); 452 struct dquot *dquot = get_empty_dquot(); 453 454 dquot->dq_id = id; 455 dquot->dq_h = h; 456 dquot->dq_dqb.u.v2_mdqb.dqb_off = 0; 457 memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk)); 458 459 offset = find_dqentry(h, dquot); 460 if (offset > 0) { 461 dquot->dq_dqb.u.v2_mdqb.dqb_off = offset; 462 ret = h->e2fs_read(&h->qh_qf, offset, ddquot, 463 info->dqi_entry_size); 464 if (ret != info->dqi_entry_size) { 465 if (ret > 0) 466 errno = EIO; 467 log_fatal(2, 468 "Cannot read quota structure for id %u: %s", 469 dquot->dq_id, strerror(errno)); 470 } 471 info->dqi_ops->disk2mem_dqblk(dquot, ddquot); 472 } 473 return dquot; 474} 475 476/* 477 * Scan all dquots in file and call callback on each 478 */ 479#define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7))) 480#define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7))) 481 482static int report_block(struct dquot *dquot, uint blk, char *bitmap, 483 int (*process_dquot) (struct dquot *, char *)) 484{ 485 struct qtree_mem_dqinfo *info = 486 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree; 487 dqbuf_t buf = getdqbuf(); 488 struct qt_disk_dqdbheader *dh; 489 char *ddata; 490 int entries, i; 491 492 set_bit(bitmap, blk); 493 read_blk(dquot->dq_h, blk, buf); 494 dh = (struct qt_disk_dqdbheader *)buf; 495 ddata = buf + sizeof(struct qt_disk_dqdbheader); 496 entries = __le16_to_cpu(dh->dqdh_entries); 497 for (i = 0; i < qtree_dqstr_in_blk(info); 498 i++, ddata += info->dqi_entry_size) 499 if (!qtree_entry_unused(info, ddata)) { 500 info->dqi_ops->disk2mem_dqblk(dquot, ddata); 501 if (process_dquot(dquot, NULL) < 0) 502 break; 503 } 504 freedqbuf(buf); 505 return entries; 506} 507 508static void check_reference(struct quota_handle *h, uint blk) 509{ 510 if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) 511 log_fatal(2, "Illegal reference (%u >= %u) in %s quota file. " 512 "Quota file is probably corrupted.\n" 513 "Please run e2fsck (8) to fix it.", 514 blk, 515 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks, 516 type2name(h->qh_type)); 517} 518 519static int report_tree(struct dquot *dquot, uint blk, int depth, char *bitmap, 520 int (*process_dquot) (struct dquot *, char *)) 521{ 522 int entries = 0, i; 523 dqbuf_t buf = getdqbuf(); 524 u_int32_t *ref = (u_int32_t *) buf; 525 526 read_blk(dquot->dq_h, blk, buf); 527 if (depth == QT_TREEDEPTH - 1) { 528 for (i = 0; i < QT_BLKSIZE >> 2; i++) { 529 blk = __le32_to_cpu(ref[i]); 530 check_reference(dquot->dq_h, blk); 531 if (blk && !get_bit(bitmap, blk)) 532 entries += report_block(dquot, blk, bitmap, 533 process_dquot); 534 } 535 } else { 536 for (i = 0; i < QT_BLKSIZE >> 2; i++) 537 blk = __le32_to_cpu(ref[i]); 538 if (blk) { 539 check_reference(dquot->dq_h, blk); 540 entries += report_tree(dquot, blk, depth + 1, 541 bitmap, process_dquot); 542 } 543 } 544 freedqbuf(buf); 545 return entries; 546} 547 548static uint find_set_bits(char *bmp, int blocks) 549{ 550 uint i, used = 0; 551 552 for (i = 0; i < blocks; i++) 553 if (get_bit(bmp, i)) 554 used++; 555 return used; 556} 557 558int qtree_scan_dquots(struct quota_handle *h, 559 int (*process_dquot) (struct dquot *, char *)) 560{ 561 char *bitmap; 562 struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi; 563 struct qtree_mem_dqinfo *info = &v2info->dqi_qtree; 564 struct dquot *dquot = get_empty_dquot(); 565 566 dquot->dq_h = h; 567 bitmap = smalloc((info->dqi_blocks + 7) >> 3); 568 memset(bitmap, 0, (info->dqi_blocks + 7) >> 3); 569 v2info->dqi_used_entries = report_tree(dquot, QT_TREEOFF, 0, bitmap, 570 process_dquot); 571 v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks); 572 free(bitmap); 573 free(dquot); 574 return 0; 575} 576