Rev 3517 | Rev 3521 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
3504 | jermar | 1 | /* |
2 | * Copyright (c) 2008 Jakub Jermar |
||
3 | * All rights reserved. |
||
4 | * |
||
5 | * Redistribution and use in source and binary forms, with or without |
||
6 | * modification, are permitted provided that the following conditions |
||
7 | * are met: |
||
8 | * |
||
9 | * - Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * - Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * - The name of the author may not be used to endorse or promote products |
||
15 | * derived from this software without specific prior written permission. |
||
16 | * |
||
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
||
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
||
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
||
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
||
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
||
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
||
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
||
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
||
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
27 | */ |
||
28 | |||
29 | /** @addtogroup fs |
||
30 | * @{ |
||
31 | */ |
||
32 | |||
33 | /** |
||
34 | * @file fat_fat.c |
||
3517 | jermar | 35 | * @brief Functions that manipulate the File Allocation Tables. |
3504 | jermar | 36 | */ |
37 | |||
3506 | jermar | 38 | #include "fat_fat.h" |
39 | #include "fat_dentry.h" |
||
40 | #include "fat.h" |
||
41 | #include "../../vfs/vfs.h" |
||
42 | #include <libfs.h> |
||
43 | #include <errno.h> |
||
44 | #include <byteorder.h> |
||
45 | #include <align.h> |
||
46 | #include <assert.h> |
||
3517 | jermar | 47 | #include <futex.h> |
3504 | jermar | 48 | |
3517 | jermar | 49 | /** |
50 | * The fat_alloc_lock futex protects all copies of the File Allocation Table |
||
51 | * during allocation of clusters. The lock does not have to be held durring |
||
52 | * deallocation of clusters. |
||
53 | */ |
||
54 | static futex_t fat_alloc_lock = FUTEX_INITIALIZER; |
||
55 | |||
3518 | jermar | 56 | /** Read block from file located on a FAT file system. |
57 | * |
||
58 | * @param bs Buffer holding the boot sector of the file system. |
||
59 | * @param dev_handle Device handle of the file system. |
||
60 | * @param firstc First cluster used by the file. Can be zero if the file |
||
61 | * is empty. |
||
62 | * @param offset Offset in blocks. |
||
63 | * |
||
64 | * @return Block structure holding the requested block. |
||
65 | */ |
||
3506 | jermar | 66 | block_t * |
3516 | jermar | 67 | _fat_block_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc, |
68 | off_t offset) |
||
3506 | jermar | 69 | { |
70 | block_t *b; |
||
71 | unsigned bps; |
||
72 | unsigned spc; |
||
73 | unsigned rscnt; /* block address of the first FAT */ |
||
74 | unsigned fatcnt; |
||
75 | unsigned rde; |
||
76 | unsigned rds; /* root directory size */ |
||
77 | unsigned sf; |
||
78 | unsigned ssa; /* size of the system area */ |
||
79 | unsigned clusters; |
||
80 | fat_cluster_t clst = firstc; |
||
81 | unsigned i; |
||
82 | |||
3516 | jermar | 83 | bps = uint16_t_le2host(bs->bps); |
84 | spc = bs->spc; |
||
85 | rscnt = uint16_t_le2host(bs->rscnt); |
||
86 | fatcnt = bs->fatcnt; |
||
87 | rde = uint16_t_le2host(bs->root_ent_max); |
||
88 | sf = uint16_t_le2host(bs->sec_per_fat); |
||
3506 | jermar | 89 | |
90 | rds = (sizeof(fat_dentry_t) * rde) / bps; |
||
91 | rds += ((sizeof(fat_dentry_t) * rde) % bps != 0); |
||
92 | ssa = rscnt + fatcnt * sf + rds; |
||
93 | |||
94 | if (firstc == FAT_CLST_ROOT) { |
||
95 | /* root directory special case */ |
||
96 | assert(offset < rds); |
||
97 | b = block_get(dev_handle, rscnt + fatcnt * sf + offset, bps); |
||
98 | return b; |
||
99 | } |
||
100 | |||
101 | clusters = offset / spc; |
||
102 | for (i = 0; i < clusters; i++) { |
||
103 | unsigned fsec; /* sector offset relative to FAT1 */ |
||
104 | unsigned fidx; /* FAT1 entry index */ |
||
105 | |||
106 | assert(clst >= FAT_CLST_FIRST && clst < FAT_CLST_BAD); |
||
107 | fsec = (clst * sizeof(fat_cluster_t)) / bps; |
||
108 | fidx = clst % (bps / sizeof(fat_cluster_t)); |
||
109 | /* read FAT1 */ |
||
110 | b = block_get(dev_handle, rscnt + fsec, bps); |
||
111 | clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]); |
||
112 | assert(clst != FAT_CLST_BAD); |
||
113 | assert(clst < FAT_CLST_LAST1); |
||
114 | block_put(b); |
||
115 | } |
||
116 | |||
117 | b = block_get(dev_handle, ssa + (clst - FAT_CLST_FIRST) * spc + |
||
118 | offset % spc, bps); |
||
119 | |||
120 | return b; |
||
121 | } |
||
122 | |||
123 | /** Return number of blocks allocated to a file. |
||
124 | * |
||
3516 | jermar | 125 | * @param bs Buffer holding the boot sector for the file. |
3506 | jermar | 126 | * @param dev_handle Device handle of the device with the file. |
127 | * @param firstc First cluster of the file. |
||
3513 | jermar | 128 | * @param lastc If non-NULL, output argument holding the |
129 | * last cluster. |
||
3506 | jermar | 130 | * |
131 | * @return Number of blocks allocated to the file. |
||
132 | */ |
||
133 | uint16_t |
||
3516 | jermar | 134 | _fat_blcks_get(fat_bs_t *bs, dev_handle_t dev_handle, fat_cluster_t firstc, |
3513 | jermar | 135 | fat_cluster_t *lastc) |
3506 | jermar | 136 | { |
137 | block_t *b; |
||
138 | unsigned bps; |
||
139 | unsigned spc; |
||
140 | unsigned rscnt; /* block address of the first FAT */ |
||
141 | unsigned clusters = 0; |
||
142 | fat_cluster_t clst = firstc; |
||
143 | |||
3516 | jermar | 144 | bps = uint16_t_le2host(bs->bps); |
145 | spc = bs->spc; |
||
146 | rscnt = uint16_t_le2host(bs->rscnt); |
||
3506 | jermar | 147 | |
148 | if (firstc == FAT_CLST_RES0) { |
||
149 | /* No space allocated to the file. */ |
||
3513 | jermar | 150 | if (lastc) |
151 | *lastc = firstc; |
||
3506 | jermar | 152 | return 0; |
153 | } |
||
154 | |||
155 | while (clst < FAT_CLST_LAST1) { |
||
156 | unsigned fsec; /* sector offset relative to FAT1 */ |
||
157 | unsigned fidx; /* FAT1 entry index */ |
||
158 | |||
159 | assert(clst >= FAT_CLST_FIRST); |
||
3513 | jermar | 160 | if (lastc) |
161 | *lastc = clst; /* remember the last cluster */ |
||
3506 | jermar | 162 | fsec = (clst * sizeof(fat_cluster_t)) / bps; |
163 | fidx = clst % (bps / sizeof(fat_cluster_t)); |
||
164 | /* read FAT1 */ |
||
165 | b = block_get(dev_handle, rscnt + fsec, bps); |
||
166 | clst = uint16_t_le2host(((fat_cluster_t *)b->data)[fidx]); |
||
167 | assert(clst != FAT_CLST_BAD); |
||
168 | block_put(b); |
||
169 | clusters++; |
||
170 | } |
||
171 | |||
3513 | jermar | 172 | if (lastc) |
173 | *lastc = clst; |
||
3506 | jermar | 174 | return clusters * spc; |
175 | } |
||
176 | |||
177 | /** Fill the gap between EOF and a new file position. |
||
178 | * |
||
3516 | jermar | 179 | * @param bs Buffer holding the boot sector for nodep. |
3506 | jermar | 180 | * @param nodep FAT node with the gap. |
181 | * @param mcl First cluster in an independent cluster chain that will |
||
182 | * be later appended to the end of the node's own cluster |
||
183 | * chain. If pos is still in the last allocated cluster, |
||
184 | * this argument is ignored. |
||
185 | * @param pos Position in the last node block. |
||
186 | */ |
||
3516 | jermar | 187 | void fat_fill_gap(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl, off_t pos) |
3506 | jermar | 188 | { |
189 | uint16_t bps; |
||
190 | unsigned spc; |
||
3516 | jermar | 191 | block_t *b; |
3506 | jermar | 192 | off_t o, boundary; |
193 | |||
3516 | jermar | 194 | bps = uint16_t_le2host(bs->bps); |
195 | spc = bs->spc; |
||
3506 | jermar | 196 | |
197 | boundary = ROUND_UP(nodep->size, bps * spc); |
||
198 | |||
199 | /* zero out already allocated space */ |
||
200 | for (o = nodep->size - 1; o < pos && o < boundary; |
||
201 | o = ALIGN_DOWN(o + bps, bps)) { |
||
3516 | jermar | 202 | b = fat_block_get(bs, nodep, o / bps); |
3506 | jermar | 203 | memset(b->data + o % bps, 0, bps - o % bps); |
204 | b->dirty = true; /* need to sync node */ |
||
205 | block_put(b); |
||
206 | } |
||
207 | |||
208 | if (o >= pos) |
||
209 | return; |
||
210 | |||
211 | /* zero out the initial part of the new cluster chain */ |
||
212 | for (o = boundary; o < pos; o += bps) { |
||
3516 | jermar | 213 | b = _fat_block_get(bs, nodep->idx->dev_handle, mcl, |
3506 | jermar | 214 | (o - boundary) / bps); |
215 | memset(b->data, 0, min(bps, pos - o)); |
||
216 | b->dirty = true; /* need to sync node */ |
||
217 | block_put(b); |
||
218 | } |
||
219 | } |
||
220 | |||
3518 | jermar | 221 | /** Mark cluster in one instance of FAT. |
222 | * |
||
223 | * @param bs Buffer holding the boot sector for the file system. |
||
224 | * @param dev_handle Device handle for the file system. |
||
225 | * @param fatno Number of the FAT instance where to make the change. |
||
226 | * @param clst Cluster which is to be marked. |
||
227 | * @param value Value mark the cluster with. |
||
228 | */ |
||
3506 | jermar | 229 | void |
3516 | jermar | 230 | fat_mark_cluster(fat_bs_t *bs, dev_handle_t dev_handle, unsigned fatno, |
231 | fat_cluster_t clst, fat_cluster_t value) |
||
3506 | jermar | 232 | { |
3516 | jermar | 233 | block_t *b; |
3510 | jermar | 234 | uint16_t bps; |
235 | uint16_t rscnt; |
||
236 | uint16_t sf; |
||
237 | fat_cluster_t *cp; |
||
238 | |||
3516 | jermar | 239 | bps = uint16_t_le2host(bs->bps); |
240 | rscnt = uint16_t_le2host(bs->rscnt); |
||
241 | sf = uint16_t_le2host(bs->sec_per_fat); |
||
3510 | jermar | 242 | |
3516 | jermar | 243 | assert(fatno < bs->fatcnt); |
244 | b = block_get(dev_handle, rscnt + sf * fatno + |
||
3510 | jermar | 245 | (clst * sizeof(fat_cluster_t)) / bps, bps); |
3516 | jermar | 246 | cp = (fat_cluster_t *)b->data + clst % (bps / sizeof(fat_cluster_t)); |
3510 | jermar | 247 | *cp = host2uint16_t_le(value); |
3516 | jermar | 248 | b->dirty = true; /* need to sync block */ |
249 | block_put(b); |
||
3506 | jermar | 250 | } |
251 | |||
3518 | jermar | 252 | /** Replay the allocatoin of clusters in all shadow instances of FAT. |
253 | * |
||
254 | * @param bs Buffer holding the boot sector of the file system. |
||
255 | * @param dev_handle Device handle of the file system. |
||
256 | * @param lifo Chain of allocated clusters. |
||
257 | * @param nclsts Number of clusters in the lifo chain. |
||
258 | */ |
||
3516 | jermar | 259 | void fat_alloc_shadow_clusters(fat_bs_t *bs, dev_handle_t dev_handle, |
260 | fat_cluster_t *lifo, unsigned nclsts) |
||
3506 | jermar | 261 | { |
3507 | jermar | 262 | uint8_t fatno; |
263 | unsigned c; |
||
264 | |||
3516 | jermar | 265 | for (fatno = FAT1 + 1; fatno < bs->fatcnt; fatno++) { |
3507 | jermar | 266 | for (c = 0; c < nclsts; c++) { |
3516 | jermar | 267 | fat_mark_cluster(bs, dev_handle, fatno, lifo[c], |
3507 | jermar | 268 | c == 0 ? FAT_CLST_LAST1 : lifo[c - 1]); |
269 | } |
||
270 | } |
||
3506 | jermar | 271 | } |
272 | |||
3518 | jermar | 273 | /** Allocate clusters in FAT1. |
274 | * |
||
275 | * This function will attempt to allocate the requested number of clusters in |
||
276 | * the first FAT instance. The FAT will be altered so that the allocated |
||
277 | * clusters form an independent chain (i.e. a chain which does not belong to any |
||
278 | * file yet). |
||
279 | * |
||
280 | * @param bs Buffer holding the boot sector of the file system. |
||
281 | * @param dev_handle Device handle of the file system. |
||
282 | * @param nclsts Number of clusters to allocate. |
||
283 | * @param mcl Output parameter where the first cluster in the chain |
||
284 | * will be returned. |
||
285 | * @param lcl Output parameter where the last cluster in the chain |
||
286 | * will be returned. |
||
287 | * |
||
288 | * @return EOK on success, a negative error code otherwise. |
||
289 | */ |
||
3506 | jermar | 290 | int |
3516 | jermar | 291 | fat_alloc_clusters(fat_bs_t *bs, dev_handle_t dev_handle, unsigned nclsts, |
292 | fat_cluster_t *mcl, fat_cluster_t *lcl) |
||
3506 | jermar | 293 | { |
294 | uint16_t bps; |
||
295 | uint16_t rscnt; |
||
296 | uint16_t sf; |
||
3516 | jermar | 297 | block_t *blk; |
3506 | jermar | 298 | fat_cluster_t *lifo; /* stack for storing free cluster numbers */ |
299 | unsigned found = 0; /* top of the free cluster number stack */ |
||
300 | unsigned b, c, cl; |
||
301 | |||
302 | lifo = (fat_cluster_t *) malloc(nclsts * sizeof(fat_cluster_t)); |
||
303 | if (lifo) |
||
304 | return ENOMEM; |
||
305 | |||
3516 | jermar | 306 | bps = uint16_t_le2host(bs->bps); |
307 | rscnt = uint16_t_le2host(bs->rscnt); |
||
308 | sf = uint16_t_le2host(bs->sec_per_fat); |
||
3506 | jermar | 309 | |
310 | /* |
||
311 | * Search FAT1 for unused clusters. |
||
312 | */ |
||
3517 | jermar | 313 | futex_down(&fat_alloc_lock); |
3506 | jermar | 314 | for (b = 0, cl = 0; b < sf; blk++) { |
315 | blk = block_get(dev_handle, rscnt + b, bps); |
||
316 | for (c = 0; c < bps / sizeof(fat_cluster_t); c++, cl++) { |
||
317 | fat_cluster_t *clst = (fat_cluster_t *)blk->data + c; |
||
3512 | jermar | 318 | if (uint16_t_le2host(*clst) == FAT_CLST_RES0) { |
3506 | jermar | 319 | /* |
320 | * The cluster is free. Put it into our stack |
||
321 | * of found clusters and mark it as non-free. |
||
322 | */ |
||
323 | lifo[found] = cl; |
||
3512 | jermar | 324 | *clst = (found == 0) ? |
325 | host2uint16_t_le(FAT_CLST_LAST1) : |
||
326 | host2uint16_t_le(lifo[found - 1]); |
||
3506 | jermar | 327 | blk->dirty = true; /* need to sync block */ |
328 | if (++found == nclsts) { |
||
329 | /* we are almost done */ |
||
330 | block_put(blk); |
||
331 | /* update the shadow copies of FAT */ |
||
3516 | jermar | 332 | fat_alloc_shadow_clusters(bs, |
333 | dev_handle, lifo, nclsts); |
||
3506 | jermar | 334 | *mcl = lifo[found - 1]; |
335 | *lcl = lifo[0]; |
||
336 | free(lifo); |
||
3517 | jermar | 337 | futex_up(&fat_alloc_lock); |
3506 | jermar | 338 | return EOK; |
339 | } |
||
340 | } |
||
341 | } |
||
342 | block_put(blk); |
||
343 | } |
||
3517 | jermar | 344 | futex_up(&fat_alloc_lock); |
3506 | jermar | 345 | |
346 | /* |
||
347 | * We could not find enough clusters. Now we need to free the clusters |
||
348 | * we have allocated so far. |
||
349 | */ |
||
3516 | jermar | 350 | while (found--) { |
351 | fat_mark_cluster(bs, dev_handle, FAT1, lifo[found], |
||
352 | FAT_CLST_RES0); |
||
353 | } |
||
3506 | jermar | 354 | |
355 | free(lifo); |
||
356 | return ENOSPC; |
||
357 | } |
||
358 | |||
3518 | jermar | 359 | /** Append a cluster chain to the last file cluster in all FATs. |
360 | * |
||
361 | * @param bs Buffer holding boot sector of the file system. |
||
362 | * @param nodep Node representing the file. |
||
363 | * @param mcl First cluster of the cluster chain to append. |
||
364 | */ |
||
3516 | jermar | 365 | void fat_append_clusters(fat_bs_t *bs, fat_node_t *nodep, fat_cluster_t mcl) |
3506 | jermar | 366 | { |
3516 | jermar | 367 | dev_handle_t dev_handle = nodep->idx->dev_handle; |
3513 | jermar | 368 | fat_cluster_t lcl; |
3516 | jermar | 369 | uint8_t fatno; |
3513 | jermar | 370 | |
3516 | jermar | 371 | if (_fat_blcks_get(bs, dev_handle, nodep->firstc, &lcl) == 0) { |
3513 | jermar | 372 | nodep->firstc = host2uint16_t_le(mcl); |
373 | nodep->dirty = true; /* need to sync node */ |
||
374 | return; |
||
375 | } |
||
376 | |||
3516 | jermar | 377 | for (fatno = FAT1; fatno < bs->fatcnt; fatno++) |
378 | fat_mark_cluster(bs, nodep->idx->dev_handle, fatno, lcl, mcl); |
||
3506 | jermar | 379 | } |
380 | |||
3504 | jermar | 381 | /** |
382 | * @} |
||
383 | */ |