1/* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include <assert.h> 18#include <string.h> 19#include <endian.h> 20 21#include "fatblock.h" 22#include "fat.h" 23#include "fs.h" 24#include "utils.h" 25 26#define DEFAULT_SECTOR_SIZE 512 27 28static void fs_add_extent(struct fs *fs, struct extent *extent, 29 offset_t start, offset_t len, int type) 30{ 31 assert(fs); 32 assert(extent); 33 34 extent->start = start; 35 extent->len = len; 36 extent->type = type; 37 38 extent->next = fs->extents; 39 fs->extents = extent; 40} 41 42struct extent *fs_find_extent(struct fs *fs, offset_t start, offset_t len, 43 struct extent *last, 44 offset_t *r_start_out, 45 offset_t *e_start_out, 46 offset_t *len_out) 47{ 48 struct extent *e; 49 offset_t end; 50 offset_t e_start, e_end, e_len, e_rel_start, r_rel_start, rel_len; 51 52 assert(fs); 53 54 end = start + len; 55 56 e = last ? last->next : fs->extents; 57 for (; e; e = e->next) { 58 e_start = e->start; 59 e_len = e->len; 60 e_end = e_start + e_len; 61 62 if (start >= e_end) 63 continue; 64 65 if (end <= e_start) 66 continue; 67 68 if (e_start <= start) { 69 r_rel_start = 0; 70 e_rel_start = start - e_start; 71 if (end <= e_end) 72 rel_len = len; 73 else 74 rel_len = e_end - start; 75 } else { 76 e_rel_start = 0; 77 r_rel_start = e_start - start; 78 if (e_end <= end) 79 rel_len = e_len; 80 else 81 rel_len = end - e_start; 82 } 83 84 assert(e_rel_start < e_len); 85 assert(e_rel_start + rel_len <= e_len); 86 assert(r_rel_start < len); 87 assert(r_rel_start + rel_len <= len); 88 89 if (r_start_out) 90 *r_start_out = r_rel_start; 91 if (e_start_out) 92 *e_start_out = e_rel_start; 93 if (len_out) 94 *len_out = rel_len; 95 96 return e; 97 } 98 99 return NULL; 100} 101 102static void fs_set_fat(struct fs *fs, cluster_t cluster, fat_entry_t entry) 103{ 104 assert(fs); 105 106 fs->fat[cluster] = htole32(entry); 107} 108 109int fs_alloc_extent(struct fs *fs, struct extent *extent, 110 offset_t len, int type, cluster_t *first_cluster_out) 111{ 112 assert(fs); 113 assert(extent); 114 115 cluster_t clusters_needed, start; 116 cluster_t i; 117 118 if (len == 0) { 119 extent->start = 0; 120 extent->len = 0; 121 extent->type = type; 122 *first_cluster_out = 0; 123 return 0; 124 } 125 126 clusters_needed = (len + fs->cluster_size - 1) / fs->cluster_size; 127 128 /* Check for adequate space. */ 129 if (fs->next_cluster + clusters_needed > fs->num_clusters) { 130 WARN("allocating extent: filesystem is full!\n"); 131 return -1; 132 } 133 134 /* Allocate clusters. */ 135 start = fs->next_cluster; 136 fs->next_cluster += clusters_needed; 137 138 /* Update FAT. */ 139 for (i = 0; i < clusters_needed - 1; i++) { 140 fs_set_fat(fs, start + i, start + i + 1); 141 } 142 fs_set_fat(fs, start + clusters_needed - 1, FAT_ENTRY_EOC); 143 144 *first_cluster_out = start; 145 146 fs_add_extent(fs, 147 extent, 148 fs->data_offset + (offset_t)(start - FAT_CLUSTER_ZERO) 149 * fs->cluster_size, 150 (offset_t)clusters_needed * fs->cluster_size, 151 type); 152 153 return 0; 154} 155 156int fs_init(struct fs *fs, uint16_t cluster_size, offset_t data_size, 157 offset_t *total_size_out) 158{ 159 uint16_t sector_size; 160 cluster_t data_clusters; 161 sector_t reserved_sectors, fat_sectors, data_sectors, total_sectors; 162 sector_t sectors_per_cluster; 163 int fat_entries_per_sector; 164 fat_entry_t *fat; 165 struct fat_boot_sector *bs; 166 struct fat_info_sector *is; 167 168 assert(fs); 169 170 sector_size = DEFAULT_SECTOR_SIZE; 171 fs->cluster_size = cluster_size; 172 173 sectors_per_cluster = cluster_size / DEFAULT_SECTOR_SIZE; 174 fat_entries_per_sector = sector_size / sizeof(fat_entry_t); 175 176 data_clusters = (data_size + cluster_size - 1) / cluster_size; 177 data_sectors = data_clusters * sectors_per_cluster; 178 fat_sectors = ((data_clusters + 2) + fat_entries_per_sector - 1) 179 / fat_entries_per_sector; 180 reserved_sectors = 3; 181 total_sectors = reserved_sectors + fat_sectors + data_sectors; 182 183 memset(&fs->boot, 0, sizeof(fs->boot)); 184 bs = &fs->boot; 185 186 strpadcpy(bs->name, "FATBLOCK", ' ', sizeof(bs->name)); 187 bs->sector_size = htole16(sector_size); 188 bs->sectors_per_cluster = sectors_per_cluster; 189 bs->reserved_sectors = htole16(reserved_sectors); 190 bs->fats = 1; 191 bs->media_desc = FAT_MEDIA_DESC_FIXED; 192 /* TODO: Calculate geometry? */ 193 bs->sectors_per_track = htole16(42); 194 bs->heads = htole16(42); 195 bs->sectors32 = htole32(total_sectors); 196 bs->fat_sectors32 = htole32(fat_sectors); 197 /* bs->rootdir_start will be set later. */ 198 bs->fs_info_sector = htole16(1); 199 bs->backup_boot_sector = htole16(2); 200 bs->phys_drive = FAT_PHYS_DRIVE_REMOVABLE; 201 bs->ext_boot_sig = FAT_EXT_BOOT_SIG; 202 bs->serial = 0x42424242; 203 strpadcpy(bs->vol_label, "FATBLOCK", ' ', sizeof(bs->vol_label)); 204 strpadcpy(bs->type, "FAT32", ' ', sizeof(bs->type)); 205 memcpy(bs->boot_sig, FAT_BOOT_SIG, sizeof(bs->boot_sig)); 206 207 memset(&fs->info, 0, sizeof(fs->info)); 208 is = &fs->info; 209 210 memcpy(is->info_sig1, FAT_INFO_SIG1, sizeof(is->info_sig1)); 211 memcpy(is->info_sig2, FAT_INFO_SIG2, sizeof(is->info_sig2)); 212 is->free_clusters = htole32(-1); 213 is->last_cluster = htole32(FAT_CLUSTER_ZERO); 214 memcpy(is->info_sig3, FAT_INFO_SIG3, sizeof(is->info_sig3)); 215 216 fs->num_clusters = FAT_CLUSTER_ZERO + data_clusters; 217 fs->next_cluster = FAT_CLUSTER_ZERO; 218 219 fs->fat_size = fat_sectors * sector_size; 220 fs->fat = malloc(fs->fat_size); 221 if (!fs->fat) { 222 WARN("initializing filesystem: couldn't allocate FAT extent: " 223 "out of memory\n"); 224 return MALLOC_FAIL; 225 } 226 memset(fs->fat, 0, fs->fat_size); 227 228 fs->data_offset = (reserved_sectors + fat_sectors) * sector_size; 229 230 fs->extents = NULL; 231 fs_add_extent(fs, &fs->boot_extent, 232 0, sector_size, 233 EXTENT_TYPE_BOOT); 234 fs_add_extent(fs, &fs->info_extent, 235 sector_size, sector_size, 236 EXTENT_TYPE_INFO); 237 fs_add_extent(fs, &fs->backup_boot_extent, 238 2 * sector_size, sector_size, 239 EXTENT_TYPE_BOOT); 240 fs_add_extent(fs, &fs->fat_extent, 241 reserved_sectors * sector_size, fs->fat_size, 242 EXTENT_TYPE_FAT); 243 244 *total_size_out = (offset_t)total_sectors * sector_size; 245 246 return 0; 247} 248 249void fs_set_rootdir_start(struct fs *fs, cluster_t rootdir_start) 250{ 251 assert(fs); 252 253 fs->boot.rootdir_start = htole32(rootdir_start); 254} 255 256void fs_update_free_clusters(struct fs *fs) 257{ 258 assert(fs); 259 260 fs->info.free_clusters = htole32(fs->num_clusters - fs->next_cluster); 261} 262