1*9eefe2a2SStefan Roese /* 2*9eefe2a2SStefan Roese * This file is part of UBIFS. 3*9eefe2a2SStefan Roese * 4*9eefe2a2SStefan Roese * Copyright (C) 2006-2008 Nokia Corporation. 5*9eefe2a2SStefan Roese * 6*9eefe2a2SStefan Roese * This program is free software; you can redistribute it and/or modify it 7*9eefe2a2SStefan Roese * under the terms of the GNU General Public License version 2 as published by 8*9eefe2a2SStefan Roese * the Free Software Foundation. 9*9eefe2a2SStefan Roese * 10*9eefe2a2SStefan Roese * This program is distributed in the hope that it will be useful, but WITHOUT 11*9eefe2a2SStefan Roese * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12*9eefe2a2SStefan Roese * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 13*9eefe2a2SStefan Roese * more details. 14*9eefe2a2SStefan Roese * 15*9eefe2a2SStefan Roese * You should have received a copy of the GNU General Public License along with 16*9eefe2a2SStefan Roese * this program; if not, write to the Free Software Foundation, Inc., 51 17*9eefe2a2SStefan Roese * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 18*9eefe2a2SStefan Roese * 19*9eefe2a2SStefan Roese * Authors: Adrian Hunter 20*9eefe2a2SStefan Roese * Artem Bityutskiy (Битюцкий Артём) 21*9eefe2a2SStefan Roese */ 22*9eefe2a2SStefan Roese 23*9eefe2a2SStefan Roese /* 24*9eefe2a2SStefan Roese * This file implements the budgeting sub-system which is responsible for UBIFS 25*9eefe2a2SStefan Roese * space management. 26*9eefe2a2SStefan Roese * 27*9eefe2a2SStefan Roese * Factors such as compression, wasted space at the ends of LEBs, space in other 28*9eefe2a2SStefan Roese * journal heads, the effect of updates on the index, and so on, make it 29*9eefe2a2SStefan Roese * impossible to accurately predict the amount of space needed. Consequently 30*9eefe2a2SStefan Roese * approximations are used. 31*9eefe2a2SStefan Roese */ 32*9eefe2a2SStefan Roese 33*9eefe2a2SStefan Roese #include "ubifs.h" 34*9eefe2a2SStefan Roese #include <linux/math64.h> 35*9eefe2a2SStefan Roese 36*9eefe2a2SStefan Roese /** 37*9eefe2a2SStefan Roese * ubifs_calc_min_idx_lebs - calculate amount of eraseblocks for the index. 38*9eefe2a2SStefan Roese * @c: UBIFS file-system description object 39*9eefe2a2SStefan Roese * 40*9eefe2a2SStefan Roese * This function calculates and returns the number of eraseblocks which should 41*9eefe2a2SStefan Roese * be kept for index usage. 42*9eefe2a2SStefan Roese */ 43*9eefe2a2SStefan Roese int ubifs_calc_min_idx_lebs(struct ubifs_info *c) 44*9eefe2a2SStefan Roese { 45*9eefe2a2SStefan Roese int idx_lebs, eff_leb_size = c->leb_size - c->max_idx_node_sz; 46*9eefe2a2SStefan Roese long long idx_size; 47*9eefe2a2SStefan Roese 48*9eefe2a2SStefan Roese idx_size = c->old_idx_sz + c->budg_idx_growth + c->budg_uncommitted_idx; 49*9eefe2a2SStefan Roese 50*9eefe2a2SStefan Roese /* And make sure we have thrice the index size of space reserved */ 51*9eefe2a2SStefan Roese idx_size = idx_size + (idx_size << 1); 52*9eefe2a2SStefan Roese 53*9eefe2a2SStefan Roese /* 54*9eefe2a2SStefan Roese * We do not maintain 'old_idx_size' as 'old_idx_lebs'/'old_idx_bytes' 55*9eefe2a2SStefan Roese * pair, nor similarly the two variables for the new index size, so we 56*9eefe2a2SStefan Roese * have to do this costly 64-bit division on fast-path. 57*9eefe2a2SStefan Roese */ 58*9eefe2a2SStefan Roese idx_size += eff_leb_size - 1; 59*9eefe2a2SStefan Roese idx_lebs = div_u64(idx_size, eff_leb_size); 60*9eefe2a2SStefan Roese /* 61*9eefe2a2SStefan Roese * The index head is not available for the in-the-gaps method, so add an 62*9eefe2a2SStefan Roese * extra LEB to compensate. 63*9eefe2a2SStefan Roese */ 64*9eefe2a2SStefan Roese idx_lebs += 1; 65*9eefe2a2SStefan Roese if (idx_lebs < MIN_INDEX_LEBS) 66*9eefe2a2SStefan Roese idx_lebs = MIN_INDEX_LEBS; 67*9eefe2a2SStefan Roese return idx_lebs; 68*9eefe2a2SStefan Roese } 69*9eefe2a2SStefan Roese 70*9eefe2a2SStefan Roese /** 71*9eefe2a2SStefan Roese * ubifs_reported_space - calculate reported free space. 72*9eefe2a2SStefan Roese * @c: the UBIFS file-system description object 73*9eefe2a2SStefan Roese * @free: amount of free space 74*9eefe2a2SStefan Roese * 75*9eefe2a2SStefan Roese * This function calculates amount of free space which will be reported to 76*9eefe2a2SStefan Roese * user-space. User-space application tend to expect that if the file-system 77*9eefe2a2SStefan Roese * (e.g., via the 'statfs()' call) reports that it has N bytes available, they 78*9eefe2a2SStefan Roese * are able to write a file of size N. UBIFS attaches node headers to each data 79*9eefe2a2SStefan Roese * node and it has to write indexing nodes as well. This introduces additional 80*9eefe2a2SStefan Roese * overhead, and UBIFS has to report slightly less free space to meet the above 81*9eefe2a2SStefan Roese * expectations. 82*9eefe2a2SStefan Roese * 83*9eefe2a2SStefan Roese * This function assumes free space is made up of uncompressed data nodes and 84*9eefe2a2SStefan Roese * full index nodes (one per data node, tripled because we always allow enough 85*9eefe2a2SStefan Roese * space to write the index thrice). 86*9eefe2a2SStefan Roese * 87*9eefe2a2SStefan Roese * Note, the calculation is pessimistic, which means that most of the time 88*9eefe2a2SStefan Roese * UBIFS reports less space than it actually has. 89*9eefe2a2SStefan Roese */ 90*9eefe2a2SStefan Roese long long ubifs_reported_space(const struct ubifs_info *c, long long free) 91*9eefe2a2SStefan Roese { 92*9eefe2a2SStefan Roese int divisor, factor, f; 93*9eefe2a2SStefan Roese 94*9eefe2a2SStefan Roese /* 95*9eefe2a2SStefan Roese * Reported space size is @free * X, where X is UBIFS block size 96*9eefe2a2SStefan Roese * divided by UBIFS block size + all overhead one data block 97*9eefe2a2SStefan Roese * introduces. The overhead is the node header + indexing overhead. 98*9eefe2a2SStefan Roese * 99*9eefe2a2SStefan Roese * Indexing overhead calculations are based on the following formula: 100*9eefe2a2SStefan Roese * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number 101*9eefe2a2SStefan Roese * of data nodes, f - fanout. Because effective UBIFS fanout is twice 102*9eefe2a2SStefan Roese * as less than maximum fanout, we assume that each data node 103*9eefe2a2SStefan Roese * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes. 104*9eefe2a2SStefan Roese * Note, the multiplier 3 is because UBIFS reserves thrice as more space 105*9eefe2a2SStefan Roese * for the index. 106*9eefe2a2SStefan Roese */ 107*9eefe2a2SStefan Roese f = c->fanout > 3 ? c->fanout >> 1 : 2; 108*9eefe2a2SStefan Roese factor = UBIFS_BLOCK_SIZE; 109*9eefe2a2SStefan Roese divisor = UBIFS_MAX_DATA_NODE_SZ; 110*9eefe2a2SStefan Roese divisor += (c->max_idx_node_sz * 3) / (f - 1); 111*9eefe2a2SStefan Roese free *= factor; 112*9eefe2a2SStefan Roese return div_u64(free, divisor); 113*9eefe2a2SStefan Roese } 114