fatblock/fs.c

   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 <sys/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
  28 static 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
  42 struct 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
 102 static 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
 109 int 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
 156 int 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
 249 void 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
 256 void 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 }