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