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
fs_add_extent(struct fs * fs,struct extent * extent,offset_t start,offset_t len,int type)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
fs_find_extent(struct fs * fs,offset_t start,offset_t len,struct extent * last,offset_t * r_start_out,offset_t * e_start_out,offset_t * len_out)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
fs_set_fat(struct fs * fs,cluster_t cluster,fat_entry_t entry)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
fs_alloc_extent(struct fs * fs,struct extent * extent,offset_t len,int type,cluster_t * first_cluster_out)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
fs_init(struct fs * fs,uint16_t cluster_size,offset_t data_size,offset_t * total_size_out)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
fs_set_rootdir_start(struct fs * fs,cluster_t rootdir_start)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
fs_update_free_clusters(struct fs * fs)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 }
262