icount.c revision 641b66bc7ee0a880b0eb0125dff5f8ed8dd5a160
1/* 2 * icount.c --- an efficient inode count abstraction 3 * 4 * Copyright (C) 1997 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 */ 11 12#if HAVE_UNISTD_H 13#include <unistd.h> 14#endif 15#include <string.h> 16#include <stdio.h> 17 18#include "ext2_fs.h" 19#include "ext2fs.h" 20 21/* 22 * The data storage strategy used by icount relies on the observation 23 * that most inode counts are either zero (for non-allocated inodes), 24 * one (for most files), and only a few that are two or more 25 * (directories and files that are linked to more than one directory). 26 * 27 * Also, e2fsck tends to load the icount data sequentially. 28 * 29 * So, we use an inode bitmap to indicate which inodes have a count of 30 * one, and then use a sorted list to store the counts for inodes 31 * which are greater than one. 32 * 33 * We also use an optional bitmap to indicate which inodes are already 34 * in the sorted list, to speed up the use of this abstraction by 35 * e2fsck's pass 2. Pass 2 increments inode counts as it finds them, 36 * so this extra bitmap avoids searching the sorted list to see if a 37 * particular inode is on the sorted list already. 38 */ 39 40struct ext2_icount_el { 41 ext2_ino_t ino; 42 __u16 count; 43}; 44 45struct ext2_icount { 46 errcode_t magic; 47 ext2fs_inode_bitmap single; 48 ext2fs_inode_bitmap multiple; 49 ext2_ino_t count; 50 ext2_ino_t size; 51 ext2_ino_t num_inodes; 52 ext2_ino_t cursor; 53 struct ext2_icount_el *list; 54}; 55 56void ext2fs_free_icount(ext2_icount_t icount) 57{ 58 if (!icount) 59 return; 60 61 icount->magic = 0; 62 if (icount->list) 63 ext2fs_free_mem(&icount->list); 64 if (icount->single) 65 ext2fs_free_inode_bitmap(icount->single); 66 if (icount->multiple) 67 ext2fs_free_inode_bitmap(icount->multiple); 68 ext2fs_free_mem(&icount); 69} 70 71errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size, 72 ext2_icount_t hint, ext2_icount_t *ret) 73{ 74 ext2_icount_t icount; 75 errcode_t retval; 76 size_t bytes; 77 ext2_ino_t i; 78 79 if (hint) { 80 EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT); 81 if (hint->size > size) 82 size = (size_t) hint->size; 83 } 84 85 retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount); 86 if (retval) 87 return retval; 88 memset(icount, 0, sizeof(struct ext2_icount)); 89 90 retval = ext2fs_allocate_inode_bitmap(fs, 0, 91 &icount->single); 92 if (retval) 93 goto errout; 94 95 if (flags & EXT2_ICOUNT_OPT_INCREMENT) { 96 retval = ext2fs_allocate_inode_bitmap(fs, 0, 97 &icount->multiple); 98 if (retval) 99 goto errout; 100 } else 101 icount->multiple = 0; 102 103 if (size) { 104 icount->size = size; 105 } else { 106 /* 107 * Figure out how many special case inode counts we will 108 * have. We know we will need one for each directory; 109 * we also need to reserve some extra room for file links 110 */ 111 retval = ext2fs_get_num_dirs(fs, &icount->size); 112 if (retval) 113 goto errout; 114 icount->size += fs->super->s_inodes_count / 50; 115 } 116 117 bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el)); 118#if 0 119 printf("Icount allocated %u entries, %d bytes.\n", 120 icount->size, bytes); 121#endif 122 retval = ext2fs_get_mem(bytes, &icount->list); 123 if (retval) 124 goto errout; 125 memset(icount->list, 0, bytes); 126 127 icount->magic = EXT2_ET_MAGIC_ICOUNT; 128 icount->count = 0; 129 icount->cursor = 0; 130 icount->num_inodes = fs->super->s_inodes_count; 131 132 /* 133 * Populate the sorted list with those entries which were 134 * found in the hint icount (since those are ones which will 135 * likely need to be in the sorted list this time around). 136 */ 137 if (hint) { 138 for (i=0; i < hint->count; i++) 139 icount->list[i].ino = hint->list[i].ino; 140 icount->count = hint->count; 141 } 142 143 *ret = icount; 144 return 0; 145 146errout: 147 ext2fs_free_icount(icount); 148 return(retval); 149} 150 151errcode_t ext2fs_create_icount(ext2_filsys fs, int flags, 152 unsigned int size, 153 ext2_icount_t *ret) 154{ 155 return ext2fs_create_icount2(fs, flags, size, 0, ret); 156} 157 158/* 159 * insert_icount_el() --- Insert a new entry into the sorted list at a 160 * specified position. 161 */ 162static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount, 163 ext2_ino_t ino, int pos) 164{ 165 struct ext2_icount_el *el; 166 errcode_t retval; 167 ext2_ino_t new_size = 0; 168 int num; 169 170 if (icount->count >= icount->size) { 171 if (icount->count) { 172 new_size = icount->list[(unsigned)icount->count-1].ino; 173 new_size = (ext2_ino_t) (icount->count * 174 ((float) icount->num_inodes / new_size)); 175 } 176 if (new_size < (icount->size + 100)) 177 new_size = icount->size + 100; 178#if 0 179 printf("Reallocating icount %u entries...\n", new_size); 180#endif 181 retval = ext2fs_resize_mem((size_t) icount->size * 182 sizeof(struct ext2_icount_el), 183 (size_t) new_size * 184 sizeof(struct ext2_icount_el), 185 &icount->list); 186 if (retval) 187 return 0; 188 icount->size = new_size; 189 } 190 num = (int) icount->count - pos; 191 if (num < 0) 192 return 0; /* should never happen */ 193 if (num) { 194 memmove(&icount->list[pos+1], &icount->list[pos], 195 sizeof(struct ext2_icount_el) * num); 196 } 197 icount->count++; 198 el = &icount->list[pos]; 199 el->count = 0; 200 el->ino = ino; 201 return el; 202} 203 204/* 205 * get_icount_el() --- given an inode number, try to find icount 206 * information in the sorted list. If the create flag is set, 207 * and we can't find an entry, create one in the sorted list. 208 */ 209static struct ext2_icount_el *get_icount_el(ext2_icount_t icount, 210 ext2_ino_t ino, int create) 211{ 212 float range; 213 int low, high, mid; 214 ext2_ino_t lowval, highval; 215 216 if (!icount || !icount->list) 217 return 0; 218 219 if (create && ((icount->count == 0) || 220 (ino > icount->list[(unsigned)icount->count-1].ino))) { 221 return insert_icount_el(icount, ino, (unsigned) icount->count); 222 } 223 if (icount->count == 0) 224 return 0; 225 226 if (icount->cursor >= icount->count) 227 icount->cursor = 0; 228 if (ino == icount->list[icount->cursor].ino) 229 return &icount->list[icount->cursor++]; 230#if 0 231 printf("Non-cursor get_icount_el: %u\n", ino); 232#endif 233 low = 0; 234 high = (int) icount->count-1; 235 while (low <= high) { 236#if 0 237 mid = (low+high)/2; 238#else 239 if (low == high) 240 mid = low; 241 else { 242 /* Interpolate for efficiency */ 243 lowval = icount->list[low].ino; 244 highval = icount->list[high].ino; 245 246 if (ino < lowval) 247 range = 0; 248 else if (ino > highval) 249 range = 1; 250 else { 251 range = ((float) (ino - lowval)) / 252 (highval - lowval); 253 if (range > 0.9) 254 range = 0.9; 255 if (range < 0.1) 256 range = 0.1; 257 } 258 mid = low + ((int) (range * (high-low))); 259 } 260#endif 261 if (ino == icount->list[mid].ino) { 262 icount->cursor = mid+1; 263 return &icount->list[mid]; 264 } 265 if (ino < icount->list[mid].ino) 266 high = mid-1; 267 else 268 low = mid+1; 269 } 270 /* 271 * If we need to create a new entry, it should be right at 272 * low (where high will be left at low-1). 273 */ 274 if (create) 275 return insert_icount_el(icount, ino, low); 276 return 0; 277} 278 279errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out) 280{ 281 errcode_t ret = 0; 282 unsigned int i; 283 const char *bad = "bad icount"; 284 285 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 286 287 if (icount->count > icount->size) { 288 fprintf(out, "%s: count > size\n", bad); 289 return EXT2_ET_INVALID_ARGUMENT; 290 } 291 for (i=1; i < icount->count; i++) { 292 if (icount->list[i-1].ino >= icount->list[i].ino) { 293 fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n", 294 bad, i-1, icount->list[i-1].ino, 295 i, icount->list[i].ino); 296 ret = EXT2_ET_INVALID_ARGUMENT; 297 } 298 } 299 return ret; 300} 301 302errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret) 303{ 304 struct ext2_icount_el *el; 305 306 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 307 308 if (!ino || (ino > icount->num_inodes)) 309 return EXT2_ET_INVALID_ARGUMENT; 310 311 if (ext2fs_test_inode_bitmap(icount->single, ino)) { 312 *ret = 1; 313 return 0; 314 } 315 if (icount->multiple && 316 !ext2fs_test_inode_bitmap(icount->multiple, ino)) { 317 *ret = 0; 318 return 0; 319 } 320 el = get_icount_el(icount, ino, 0); 321 if (!el) { 322 *ret = 0; 323 return 0; 324 } 325 *ret = el->count; 326 return 0; 327} 328 329errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino, 330 __u16 *ret) 331{ 332 struct ext2_icount_el *el; 333 334 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 335 336 if (!ino || (ino > icount->num_inodes)) 337 return EXT2_ET_INVALID_ARGUMENT; 338 339 if (ext2fs_test_inode_bitmap(icount->single, ino)) { 340 /* 341 * If the existing count is 1, then we know there is 342 * no entry in the list. 343 */ 344 el = get_icount_el(icount, ino, 1); 345 if (!el) 346 return EXT2_ET_NO_MEMORY; 347 ext2fs_unmark_inode_bitmap(icount->single, ino); 348 el->count = 2; 349 } else if (icount->multiple) { 350 /* 351 * The count is either zero or greater than 1; if the 352 * inode is set in icount->multiple, then there should 353 * be an entry in the list, so find it using 354 * get_icount_el(). 355 */ 356 if (ext2fs_test_inode_bitmap(icount->multiple, ino)) { 357 el = get_icount_el(icount, ino, 1); 358 if (!el) 359 return EXT2_ET_NO_MEMORY; 360 el->count++; 361 } else { 362 /* 363 * The count was zero; mark the single bitmap 364 * and return. 365 */ 366 zero_count: 367 ext2fs_mark_inode_bitmap(icount->single, ino); 368 if (ret) 369 *ret = 1; 370 return 0; 371 } 372 } else { 373 /* 374 * The count is either zero or greater than 1; try to 375 * find an entry in the list to determine which. 376 */ 377 el = get_icount_el(icount, ino, 0); 378 if (!el) { 379 /* No entry means the count was zero */ 380 goto zero_count; 381 } 382 el = get_icount_el(icount, ino, 1); 383 if (!el) 384 return EXT2_ET_NO_MEMORY; 385 el->count++; 386 } 387 if (icount->multiple) 388 ext2fs_mark_inode_bitmap(icount->multiple, ino); 389 if (ret) 390 *ret = el->count; 391 return 0; 392} 393 394errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino, 395 __u16 *ret) 396{ 397 struct ext2_icount_el *el; 398 399 if (!ino || (ino > icount->num_inodes)) 400 return EXT2_ET_INVALID_ARGUMENT; 401 402 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 403 404 if (ext2fs_test_inode_bitmap(icount->single, ino)) { 405 ext2fs_unmark_inode_bitmap(icount->single, ino); 406 if (icount->multiple) 407 ext2fs_unmark_inode_bitmap(icount->multiple, ino); 408 else { 409 el = get_icount_el(icount, ino, 0); 410 if (el) 411 el->count = 0; 412 } 413 if (ret) 414 *ret = 0; 415 return 0; 416 } 417 418 if (icount->multiple && 419 !ext2fs_test_inode_bitmap(icount->multiple, ino)) 420 return EXT2_ET_INVALID_ARGUMENT; 421 422 el = get_icount_el(icount, ino, 0); 423 if (!el || el->count == 0) 424 return EXT2_ET_INVALID_ARGUMENT; 425 426 el->count--; 427 if (el->count == 1) 428 ext2fs_mark_inode_bitmap(icount->single, ino); 429 if ((el->count == 0) && icount->multiple) 430 ext2fs_unmark_inode_bitmap(icount->multiple, ino); 431 432 if (ret) 433 *ret = el->count; 434 return 0; 435} 436 437errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino, 438 __u16 count) 439{ 440 struct ext2_icount_el *el; 441 442 if (!ino || (ino > icount->num_inodes)) 443 return EXT2_ET_INVALID_ARGUMENT; 444 445 EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 446 447 if (count == 1) { 448 ext2fs_mark_inode_bitmap(icount->single, ino); 449 if (icount->multiple) 450 ext2fs_unmark_inode_bitmap(icount->multiple, ino); 451 return 0; 452 } 453 if (count == 0) { 454 ext2fs_unmark_inode_bitmap(icount->single, ino); 455 if (icount->multiple) { 456 /* 457 * If the icount->multiple bitmap is enabled, 458 * we can just clear both bitmaps and we're done 459 */ 460 ext2fs_unmark_inode_bitmap(icount->multiple, ino); 461 } else { 462 el = get_icount_el(icount, ino, 0); 463 if (el) 464 el->count = 0; 465 } 466 return 0; 467 } 468 469 /* 470 * Get the icount element 471 */ 472 el = get_icount_el(icount, ino, 1); 473 if (!el) 474 return EXT2_ET_NO_MEMORY; 475 el->count = count; 476 ext2fs_unmark_inode_bitmap(icount->single, ino); 477 if (icount->multiple) 478 ext2fs_mark_inode_bitmap(icount->multiple, ino); 479 return 0; 480} 481 482ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount) 483{ 484 if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT) 485 return 0; 486 487 return icount->size; 488} 489