icount.c revision b5abe6fac9c9e7caf4710501d1657d30e4857ef6
119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o/* 219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * icount.c --- an efficient inode count abstraction 319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * 419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * Copyright (C) 1997 Theodore Ts'o. 519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * 619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * %Begin-Header% 719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * This file may be redistributed under the terms of the GNU Public 819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * License. 919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * %End-Header% 1019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 1119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 1219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include <et/com_err.h> 134cbe8af4b0d0c72fb28bb500c1bd8a46b00fdde3Theodore Ts'o#if HAVE_UNISTD_H 1419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include <unistd.h> 154cbe8af4b0d0c72fb28bb500c1bd8a46b00fdde3Theodore Ts'o#endif 1619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include <string.h> 1719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include <stdio.h> 1819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 19b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o#if EXT2_FLAT_INCLUDES 20b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o#include "ext2_fs.h" 21b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o#else 2219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include <linux/ext2_fs.h> 23b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o#endif 24b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o 2519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#include "ext2fs.h" 2619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 2719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o/* 2819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * The data storage strategy used by icount relies on the observation 2919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * that most inode counts are either zero (for non-allocated inodes), 3019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * one (for most files), and only a few that are two or more 3119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * (directories and files that are linked to more than one directory). 3219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * 3319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * Also, e2fsck tends to load the icount data sequentially. 3419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * 3519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * So, we use an inode bitmap to indicate which inodes have a count of 3619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * one, and then use a sorted list to store the counts for inodes 3719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * which are greater than one. 3819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * 3919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * We also use an optional bitmap to indicate which inodes are already 4019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * in the sorted list, to speed up the use of this abstraction by 4119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * e2fsck's pass 2. Pass 2 increments inode counts as it finds them, 4219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * so this extra bitmap avoids searching the sorted list to see if a 4319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * particular inode is on the sorted list already. 4419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 4519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 4619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'ostruct ext2_icount_el { 4719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ino_t ino; 4819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o __u16 count; 4919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o}; 5019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 5119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'ostruct ext2_icount { 523cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o errcode_t magic; 5319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_inode_bitmap single; 5419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_inode_bitmap multiple; 5519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ino_t count; 5619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ino_t size; 5719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ino_t num_inodes; 5819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o int cursor; 5919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o struct ext2_icount_el *list; 6019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o}; 6119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 6219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'ovoid ext2fs_free_icount(ext2_icount_t icount) 6319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 6419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!icount) 6519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return; 6619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 6719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->magic = 0; 6819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->list) 697b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o ext2fs_free_mem((void **) &icount->list); 7019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->single) 7119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_free_inode_bitmap(icount->single); 7219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) 7319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_free_inode_bitmap(icount->multiple); 747b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o ext2fs_free_mem((void **) &icount); 7519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 7619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 77521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'oerrcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, int size, 78521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ext2_icount_t hint, ext2_icount_t *ret) 7919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 8019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2_icount_t icount; 8119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o errcode_t retval; 8219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o size_t bytes; 83521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o int i; 8419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 85521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (hint) { 86521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT); 87521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (hint->size > size) 883cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o size = (size_t) hint->size; 89521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 90521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 917b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o retval = ext2fs_get_mem(sizeof(struct ext2_icount), (void **) &icount); 927b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o if (retval) 937b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o return retval; 9419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o memset(icount, 0, sizeof(struct ext2_icount)); 9519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 9619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o retval = ext2fs_allocate_inode_bitmap(fs, 0, 9719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o &icount->single); 9819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (retval) 9919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o goto errout; 10019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 10119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (flags & EXT2_ICOUNT_OPT_INCREMENT) { 10219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o retval = ext2fs_allocate_inode_bitmap(fs, 0, 10319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o &icount->multiple); 10419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (retval) 10519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o goto errout; 10619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else 10719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->multiple = 0; 10819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 10919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (size) { 11019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->size = size; 11119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else { 11219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 11319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * Figure out how many special case inode counts we will 11419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * have. We know we will need one for each directory; 11519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * we also need to reserve some extra room for file links 11619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 11719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o retval = ext2fs_get_num_dirs(fs, &icount->size); 11819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (retval) 11919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o goto errout; 12019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->size += fs->super->s_inodes_count / 50; 12119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 12219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 1233cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el)); 12419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#if 0 12519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o printf("Icount allocated %d entries, %d bytes.\n", 12619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->size, bytes); 12719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#endif 1287b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o retval = ext2fs_get_mem(bytes, (void **) &icount->list); 1297b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o if (retval) 13019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o goto errout; 13119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o memset(icount->list, 0, bytes); 13219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 13319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->magic = EXT2_ET_MAGIC_ICOUNT; 13419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->count = 0; 13519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->cursor = 0; 13619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->num_inodes = fs->super->s_inodes_count; 13719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 138521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o /* 139521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * Populate the sorted list with those entries which were 140521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * found in the hint icount (since those are ones which will 141521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * likely need to be in the sorted list this time around). 142521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o */ 143521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (hint) { 144521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o for (i=0; i < hint->count; i++) 145521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o icount->list[i].ino = hint->list[i].ino; 146521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o icount->count = hint->count; 147521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 14819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 149521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o *ret = icount; 15019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 15119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 15219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oerrout: 15319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_free_icount(icount); 15419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return(retval); 15519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 15619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 157521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'oerrcode_t ext2fs_create_icount(ext2_filsys fs, int flags, int size, 158521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ext2_icount_t *ret) 15919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 160521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return ext2fs_create_icount2(fs, flags, size, 0, ret); 16119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 16219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 16319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o/* 164521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * insert_icount_el() --- Insert a new entry into the sorted list at a 165521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * specified position. 16619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 167521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'ostatic struct ext2_icount_el *insert_icount_el(ext2_icount_t icount, 168521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ino_t ino, int pos) 16919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 1707b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o struct ext2_icount_el *el; 1717b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o errcode_t retval; 17219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ino_t new_size = 0; 173521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o int num; 17419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 17519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->count >= icount->size) { 17619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->count) { 1773cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o new_size = icount->list[(unsigned)icount->count-1].ino; 178b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o new_size = (ino_t) (icount->count * 179b5abe6fac9c9e7caf4710501d1657d30e4857ef6Theodore Ts'o ((float) new_size / icount->num_inodes)); 18019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 18119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (new_size < (icount->size + 100)) 18219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o new_size = icount->size + 100; 18319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#if 0 18419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o printf("Reallocating icount %d entries...\n", new_size); 18519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o#endif 1867b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o retval = ext2fs_resize_mem((size_t) new_size * 1877b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o sizeof(struct ext2_icount_el), 1887b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o (void **) &icount->list); 1897b4e4534f9361b21d3fafdd88a58f133decee38cTheodore Ts'o if (retval) 19019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 19119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o icount->size = new_size; 19219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 1933cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o num = (int) icount->count - pos; 194521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (num < 0) 195521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return 0; /* should never happen */ 196521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (num) { 197521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o memmove(&icount->list[pos+1], &icount->list[pos], 198521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o sizeof(struct ext2_icount_el) * num); 199521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 200521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o icount->count++; 201521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = &icount->list[pos]; 202521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el->count = 0; 203521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el->ino = ino; 204521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return el; 205521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o} 206521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 207521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o/* 208521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * get_icount_el() --- given an inode number, try to find icount 209521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * information in the sorted list. If the create flag is set, 210521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * and we can't find an entry, create one in the sorted list. 211521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o */ 212521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'ostatic struct ext2_icount_el *get_icount_el(ext2_icount_t icount, 213521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ino_t ino, int create) 214521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o{ 215521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o float range; 216521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o int low, high, mid; 217521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ino_t lowval, highval; 218521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 219521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!icount || !icount->list) 220521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return 0; 22119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 222521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (create && ((icount->count == 0) || 2233cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o (ino > icount->list[(unsigned)icount->count-1].ino))) { 2243cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o return insert_icount_el(icount, ino, (unsigned) icount->count); 225521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 226521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->count == 0) 227521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return 0; 228521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 229521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->cursor >= icount->count) 230521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o icount->cursor = 0; 231521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (ino == icount->list[icount->cursor].ino) 232521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return &icount->list[icount->cursor++]; 233521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o#if 0 234521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o printf("Non-cursor get_icount_el: %u\n", ino); 235521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o#endif 236521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o low = 0; 2373cb6c5021d722e17b7105d1bc090880671f6fc6dTheodore Ts'o high = (int) icount->count-1; 238521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o while (low <= high) { 239521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o#if 0 240521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o mid = (low+high)/2; 241521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o#else 242521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (low == high) 243521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o mid = low; 244521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o else { 245521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o /* Interpolate for efficiency */ 246521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o lowval = icount->list[low].ino; 247521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o highval = icount->list[high].ino; 248521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 249521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (ino < lowval) 250521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o range = 0; 251521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o else if (ino > highval) 252521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o range = 1; 253521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o else 254521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o range = ((float) (ino - lowval)) / 255521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o (highval - lowval); 256521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o mid = low + ((int) (range * (high-low))); 257521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 258521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o#endif 259521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (ino == icount->list[mid].ino) { 260521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o icount->cursor = mid+1; 261521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return &icount->list[mid]; 262521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 263521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (ino < icount->list[mid].ino) 264521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o high = mid-1; 265521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o else 266521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o low = mid+1; 267521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 26819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 269521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * If we need to create a new entry, it should be right at 270521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * low (where high will be left at low-1). 27119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 272521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (create) 273521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return insert_icount_el(icount, ino, low); 274521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return 0; 275521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o} 276521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 277521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'oerrcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out) 278521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o{ 279521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o errcode_t ret = 0; 280521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o int i; 281521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o const char *bad = "bad icount"; 282521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 283521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 284521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 285521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->count > icount->size) { 286521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o fprintf(out, "%s: count > size\n", bad); 2871f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 288521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 289521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o for (i=1; i < icount->count; i++) { 290521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->list[i-1].ino >= icount->list[i].ino) { 291d163b0948731e6d84bd3efe75075a2d0a8009272Theodore Ts'o fprintf(out, "%s: list[%d].ino=%ld, list[%d].ino=%ld\n", 292521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o bad, i-1, icount->list[i-1].ino, 293521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o i, icount->list[i].ino); 2941f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o ret = EXT2_ET_INVALID_ARGUMENT; 29519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 29619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 297521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return ret; 29819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 29919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 30019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oerrcode_t ext2fs_icount_fetch(ext2_icount_t icount, ino_t ino, __u16 *ret) 30119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 30219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o struct ext2_icount_el *el; 30319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 30419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 30519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 306521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!ino || (ino > icount->num_inodes)) 3071f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 308521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 30919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ext2fs_test_inode_bitmap(icount->single, ino)) { 31019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = 1; 31119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 31219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 313521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->multiple && 314521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o !ext2fs_test_inode_bitmap(icount->multiple, ino)) { 315521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o *ret = 0; 316521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o return 0; 317521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 318521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 0); 31919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!el) { 32019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = 0; 32119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 32219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 32319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = el->count; 32419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 32519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 32619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 32719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oerrcode_t ext2fs_icount_increment(ext2_icount_t icount, ino_t ino, 32819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o __u16 *ret) 32919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 33019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o struct ext2_icount_el *el; 33119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 33219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 33319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 334521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!ino || (ino > icount->num_inodes)) 3351f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 336521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 33719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ext2fs_test_inode_bitmap(icount->single, ino)) { 33819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 33919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * If the existing count is 1, then we know there is 340521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o * no entry in the list. 34119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 342521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 1); 34319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!el) 3441f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_NO_MEMORY; 345521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o ext2fs_unmark_inode_bitmap(icount->single, ino); 346521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el->count = 2; 34719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else if (icount->multiple) { 34819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 34919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * The count is either zero or greater than 1; if the 35019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * inode is set in icount->multiple, then there should 35119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * be an entry in the list, so find it using 35219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * get_icount_el(). 35319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 35419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ext2fs_test_inode_bitmap(icount->multiple, ino)) { 355521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 1); 356521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!el) 3571f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_NO_MEMORY; 358521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el->count++; 35919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else { 36019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 36119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * The count was zero; mark the single bitmap 36219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * and return. 36319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 36419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o zero_count: 36519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_mark_inode_bitmap(icount->single, ino); 36619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ret) 36719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = 1; 36819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 36919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 37019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else { 37119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 37219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * The count is either zero or greater than 1; try to 37319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * find an entry in the list to determine which. 37419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 375521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 0); 37619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!el) { 37719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* No entry means the count was zero */ 37819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o goto zero_count; 37919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 380521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 1); 38119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!el) 3821f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_NO_MEMORY; 38319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o el->count++; 384521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o } 38519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) 38619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_mark_inode_bitmap(icount->multiple, ino); 38719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ret) 38819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = el->count; 38919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 39019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 39119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 39219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oerrcode_t ext2fs_icount_decrement(ext2_icount_t icount, ino_t ino, 39319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o __u16 *ret) 39419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 39519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o struct ext2_icount_el *el; 39619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 397521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!ino || (ino > icount->num_inodes)) 3981f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 399521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 40019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 40119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 40219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ext2fs_test_inode_bitmap(icount->single, ino)) { 40319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->single, ino); 40419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) 40519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->multiple, ino); 40619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o else { 407521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 0); 40819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (el) 40919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o el->count = 0; 41019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 41119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ret) 41219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = 0; 41319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 41419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 41519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 416521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (icount->multiple && 417521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o !ext2fs_test_inode_bitmap(icount->multiple, ino)) 4181f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 419521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 420521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 0); 421521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!el || el->count == 0) 4221f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 42319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 42419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o el->count--; 42519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (el->count == 1) 42619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_mark_inode_bitmap(icount->single, ino); 42719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if ((el->count == 0) && icount->multiple) 42819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->multiple, ino); 42919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 43019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (ret) 43119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o *ret = el->count; 43219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 43319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 43419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 43519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oerrcode_t ext2fs_icount_store(ext2_icount_t icount, ino_t ino, 43619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o __u16 count) 43719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 43819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o struct ext2_icount_el *el; 43919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 440521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o if (!ino || (ino > icount->num_inodes)) 4411f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_INVALID_ARGUMENT; 442521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o 44319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT); 44419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 44519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (count == 1) { 44619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_mark_inode_bitmap(icount->single, ino); 44719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) 44819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->multiple, ino); 44919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 45019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 45119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (count == 0) { 45219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->single, ino); 45319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) { 45419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 45519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * If the icount->multiple bitmap is enabled, 45619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * we can just clear both bitmaps and we're done 45719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 45819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->multiple, ino); 45919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } else { 460521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 0); 46119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (el) 46219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o el->count = 0; 46319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 46419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 46519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o } 46619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 46719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o /* 46819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o * Get the icount element 46919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o */ 470521e36857227b21e7ab47b0a97f788d2af9f9717Theodore Ts'o el = get_icount_el(icount, ino, 1); 47119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!el) 4721f0b6c1f895d189fea6999d0c07a7fee936a4baaTheodore Ts'o return EXT2_ET_NO_MEMORY; 47319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o el->count = count; 47419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_unmark_inode_bitmap(icount->single, ino); 47519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (icount->multiple) 47619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o ext2fs_mark_inode_bitmap(icount->multiple, ino); 47719c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 47819c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 47919c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 48019c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'oino_t ext2fs_get_icount_size(ext2_icount_t icount) 48119c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o{ 48219c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT) 48319c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return 0; 48419c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o 48519c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o return icount->size; 48619c78dc07fce2d6f39b5e541562afc3ca1ea38ffTheodore Ts'o} 487