cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

balloc.c (9943B)


      1// SPDX-License-Identifier: GPL-2.0-or-later
      2/*
      3 *  Copyright (C) 2012-2013 Samsung Electronics Co., Ltd.
      4 */
      5
      6#include <linux/blkdev.h>
      7#include <linux/slab.h>
      8#include <linux/buffer_head.h>
      9
     10#include "exfat_raw.h"
     11#include "exfat_fs.h"
     12
     13static const unsigned char free_bit[] = {
     14	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*  0 ~  19*/
     15	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3,/* 20 ~  39*/
     16	0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/* 40 ~  59*/
     17	0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/* 60 ~  79*/
     18	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2,/* 80 ~  99*/
     19	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3,/*100 ~ 119*/
     20	0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*120 ~ 139*/
     21	0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5,/*140 ~ 159*/
     22	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2,/*160 ~ 179*/
     23	0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3,/*180 ~ 199*/
     24	0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2,/*200 ~ 219*/
     25	0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,/*220 ~ 239*/
     26	0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0                /*240 ~ 254*/
     27};
     28
     29static const unsigned char used_bit[] = {
     30	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3,/*  0 ~  19*/
     31	2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4,/* 20 ~  39*/
     32	2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,/* 40 ~  59*/
     33	4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,/* 60 ~  79*/
     34	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,/* 80 ~  99*/
     35	3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,/*100 ~ 119*/
     36	4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4,/*120 ~ 139*/
     37	3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,/*140 ~ 159*/
     38	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5,/*160 ~ 179*/
     39	4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,/*180 ~ 199*/
     40	3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6,/*200 ~ 219*/
     41	5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,/*220 ~ 239*/
     42	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8             /*240 ~ 255*/
     43};
     44
     45/*
     46 *  Allocation Bitmap Management Functions
     47 */
     48static int exfat_allocate_bitmap(struct super_block *sb,
     49		struct exfat_dentry *ep)
     50{
     51	struct exfat_sb_info *sbi = EXFAT_SB(sb);
     52	long long map_size;
     53	unsigned int i, need_map_size;
     54	sector_t sector;
     55
     56	sbi->map_clu = le32_to_cpu(ep->dentry.bitmap.start_clu);
     57	map_size = le64_to_cpu(ep->dentry.bitmap.size);
     58	need_map_size = ((EXFAT_DATA_CLUSTER_COUNT(sbi) - 1) / BITS_PER_BYTE)
     59		+ 1;
     60	if (need_map_size != map_size) {
     61		exfat_err(sb, "bogus allocation bitmap size(need : %u, cur : %lld)",
     62			  need_map_size, map_size);
     63		/*
     64		 * Only allowed when bogus allocation
     65		 * bitmap size is large
     66		 */
     67		if (need_map_size > map_size)
     68			return -EIO;
     69	}
     70	sbi->map_sectors = ((need_map_size - 1) >>
     71			(sb->s_blocksize_bits)) + 1;
     72	sbi->vol_amap = kmalloc_array(sbi->map_sectors,
     73				sizeof(struct buffer_head *), GFP_KERNEL);
     74	if (!sbi->vol_amap)
     75		return -ENOMEM;
     76
     77	sector = exfat_cluster_to_sector(sbi, sbi->map_clu);
     78	for (i = 0; i < sbi->map_sectors; i++) {
     79		sbi->vol_amap[i] = sb_bread(sb, sector + i);
     80		if (!sbi->vol_amap[i]) {
     81			/* release all buffers and free vol_amap */
     82			int j = 0;
     83
     84			while (j < i)
     85				brelse(sbi->vol_amap[j++]);
     86
     87			kfree(sbi->vol_amap);
     88			sbi->vol_amap = NULL;
     89			return -EIO;
     90		}
     91	}
     92
     93	return 0;
     94}
     95
     96int exfat_load_bitmap(struct super_block *sb)
     97{
     98	unsigned int i, type;
     99	struct exfat_chain clu;
    100	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    101
    102	exfat_chain_set(&clu, sbi->root_dir, 0, ALLOC_FAT_CHAIN);
    103	while (clu.dir != EXFAT_EOF_CLUSTER) {
    104		for (i = 0; i < sbi->dentries_per_clu; i++) {
    105			struct exfat_dentry *ep;
    106			struct buffer_head *bh;
    107
    108			ep = exfat_get_dentry(sb, &clu, i, &bh);
    109			if (!ep)
    110				return -EIO;
    111
    112			type = exfat_get_entry_type(ep);
    113			if (type == TYPE_UNUSED)
    114				break;
    115			if (type != TYPE_BITMAP)
    116				continue;
    117			if (ep->dentry.bitmap.flags == 0x0) {
    118				int err;
    119
    120				err = exfat_allocate_bitmap(sb, ep);
    121				brelse(bh);
    122				return err;
    123			}
    124			brelse(bh);
    125		}
    126
    127		if (exfat_get_next_cluster(sb, &clu.dir))
    128			return -EIO;
    129	}
    130
    131	return -EINVAL;
    132}
    133
    134void exfat_free_bitmap(struct exfat_sb_info *sbi)
    135{
    136	int i;
    137
    138	for (i = 0; i < sbi->map_sectors; i++)
    139		__brelse(sbi->vol_amap[i]);
    140
    141	kfree(sbi->vol_amap);
    142}
    143
    144int exfat_set_bitmap(struct inode *inode, unsigned int clu, bool sync)
    145{
    146	int i, b;
    147	unsigned int ent_idx;
    148	struct super_block *sb = inode->i_sb;
    149	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    150
    151	if (!is_valid_cluster(sbi, clu))
    152		return -EINVAL;
    153
    154	ent_idx = CLUSTER_TO_BITMAP_ENT(clu);
    155	i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx);
    156	b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx);
    157
    158	set_bit_le(b, sbi->vol_amap[i]->b_data);
    159	exfat_update_bh(sbi->vol_amap[i], sync);
    160	return 0;
    161}
    162
    163void exfat_clear_bitmap(struct inode *inode, unsigned int clu, bool sync)
    164{
    165	int i, b;
    166	unsigned int ent_idx;
    167	struct super_block *sb = inode->i_sb;
    168	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    169	struct exfat_mount_options *opts = &sbi->options;
    170
    171	if (!is_valid_cluster(sbi, clu))
    172		return;
    173
    174	ent_idx = CLUSTER_TO_BITMAP_ENT(clu);
    175	i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx);
    176	b = BITMAP_OFFSET_BIT_IN_SECTOR(sb, ent_idx);
    177
    178	clear_bit_le(b, sbi->vol_amap[i]->b_data);
    179	exfat_update_bh(sbi->vol_amap[i], sync);
    180
    181	if (opts->discard) {
    182		int ret_discard;
    183
    184		ret_discard = sb_issue_discard(sb,
    185			exfat_cluster_to_sector(sbi, clu),
    186			(1 << sbi->sect_per_clus_bits), GFP_NOFS, 0);
    187
    188		if (ret_discard == -EOPNOTSUPP) {
    189			exfat_err(sb, "discard not supported by device, disabling");
    190			opts->discard = 0;
    191		}
    192	}
    193}
    194
    195/*
    196 * If the value of "clu" is 0, it means cluster 2 which is the first cluster of
    197 * the cluster heap.
    198 */
    199unsigned int exfat_find_free_bitmap(struct super_block *sb, unsigned int clu)
    200{
    201	unsigned int i, map_i, map_b, ent_idx;
    202	unsigned int clu_base, clu_free;
    203	unsigned char k, clu_mask;
    204	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    205
    206	WARN_ON(clu < EXFAT_FIRST_CLUSTER);
    207	ent_idx = CLUSTER_TO_BITMAP_ENT(clu);
    208	clu_base = BITMAP_ENT_TO_CLUSTER(ent_idx & ~(BITS_PER_BYTE_MASK));
    209	clu_mask = IGNORED_BITS_REMAINED(clu, clu_base);
    210
    211	map_i = BITMAP_OFFSET_SECTOR_INDEX(sb, ent_idx);
    212	map_b = BITMAP_OFFSET_BYTE_IN_SECTOR(sb, ent_idx);
    213
    214	for (i = EXFAT_FIRST_CLUSTER; i < sbi->num_clusters;
    215	     i += BITS_PER_BYTE) {
    216		k = *(sbi->vol_amap[map_i]->b_data + map_b);
    217		if (clu_mask > 0) {
    218			k |= clu_mask;
    219			clu_mask = 0;
    220		}
    221		if (k < 0xFF) {
    222			clu_free = clu_base + free_bit[k];
    223			if (clu_free < sbi->num_clusters)
    224				return clu_free;
    225		}
    226		clu_base += BITS_PER_BYTE;
    227
    228		if (++map_b >= sb->s_blocksize ||
    229		    clu_base >= sbi->num_clusters) {
    230			if (++map_i >= sbi->map_sectors) {
    231				clu_base = EXFAT_FIRST_CLUSTER;
    232				map_i = 0;
    233			}
    234			map_b = 0;
    235		}
    236	}
    237
    238	return EXFAT_EOF_CLUSTER;
    239}
    240
    241int exfat_count_used_clusters(struct super_block *sb, unsigned int *ret_count)
    242{
    243	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    244	unsigned int count = 0;
    245	unsigned int i, map_i = 0, map_b = 0;
    246	unsigned int total_clus = EXFAT_DATA_CLUSTER_COUNT(sbi);
    247	unsigned int last_mask = total_clus & BITS_PER_BYTE_MASK;
    248	unsigned char clu_bits;
    249	const unsigned char last_bit_mask[] = {0, 0b00000001, 0b00000011,
    250		0b00000111, 0b00001111, 0b00011111, 0b00111111, 0b01111111};
    251
    252	total_clus &= ~last_mask;
    253	for (i = 0; i < total_clus; i += BITS_PER_BYTE) {
    254		clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b);
    255		count += used_bit[clu_bits];
    256		if (++map_b >= (unsigned int)sb->s_blocksize) {
    257			map_i++;
    258			map_b = 0;
    259		}
    260	}
    261
    262	if (last_mask) {
    263		clu_bits = *(sbi->vol_amap[map_i]->b_data + map_b);
    264		clu_bits &= last_bit_mask[last_mask];
    265		count += used_bit[clu_bits];
    266	}
    267
    268	*ret_count = count;
    269	return 0;
    270}
    271
    272int exfat_trim_fs(struct inode *inode, struct fstrim_range *range)
    273{
    274	unsigned int trim_begin, trim_end, count, next_free_clu;
    275	u64 clu_start, clu_end, trim_minlen, trimmed_total = 0;
    276	struct super_block *sb = inode->i_sb;
    277	struct exfat_sb_info *sbi = EXFAT_SB(sb);
    278	int err = 0;
    279
    280	clu_start = max_t(u64, range->start >> sbi->cluster_size_bits,
    281				EXFAT_FIRST_CLUSTER);
    282	clu_end = clu_start + (range->len >> sbi->cluster_size_bits) - 1;
    283	trim_minlen = range->minlen >> sbi->cluster_size_bits;
    284
    285	if (clu_start >= sbi->num_clusters || range->len < sbi->cluster_size)
    286		return -EINVAL;
    287
    288	if (clu_end >= sbi->num_clusters)
    289		clu_end = sbi->num_clusters - 1;
    290
    291	mutex_lock(&sbi->bitmap_lock);
    292
    293	trim_begin = trim_end = exfat_find_free_bitmap(sb, clu_start);
    294	if (trim_begin == EXFAT_EOF_CLUSTER)
    295		goto unlock;
    296
    297	next_free_clu = exfat_find_free_bitmap(sb, trim_end + 1);
    298	if (next_free_clu == EXFAT_EOF_CLUSTER)
    299		goto unlock;
    300
    301	do {
    302		if (next_free_clu == trim_end + 1) {
    303			/* extend trim range for continuous free cluster */
    304			trim_end++;
    305		} else {
    306			/* trim current range if it's larger than trim_minlen */
    307			count = trim_end - trim_begin + 1;
    308			if (count >= trim_minlen) {
    309				err = sb_issue_discard(sb,
    310					exfat_cluster_to_sector(sbi, trim_begin),
    311					count * sbi->sect_per_clus, GFP_NOFS, 0);
    312				if (err)
    313					goto unlock;
    314
    315				trimmed_total += count;
    316			}
    317
    318			/* set next start point of the free hole */
    319			trim_begin = trim_end = next_free_clu;
    320		}
    321
    322		if (next_free_clu >= clu_end)
    323			break;
    324
    325		if (fatal_signal_pending(current)) {
    326			err = -ERESTARTSYS;
    327			goto unlock;
    328		}
    329
    330		next_free_clu = exfat_find_free_bitmap(sb, next_free_clu + 1);
    331	} while (next_free_clu != EXFAT_EOF_CLUSTER &&
    332			next_free_clu > trim_end);
    333
    334	/* try to trim remainder */
    335	count = trim_end - trim_begin + 1;
    336	if (count >= trim_minlen) {
    337		err = sb_issue_discard(sb, exfat_cluster_to_sector(sbi, trim_begin),
    338			count * sbi->sect_per_clus, GFP_NOFS, 0);
    339		if (err)
    340			goto unlock;
    341
    342		trimmed_total += count;
    343	}
    344
    345unlock:
    346	mutex_unlock(&sbi->bitmap_lock);
    347	range->len = trimmed_total << sbi->cluster_size_bits;
    348
    349	return err;
    350}