xref: /openbmc/linux/fs/fat/fatent.c (revision d5cb9783536a41df9f9cba5b0a1d78047ed787f7)
1 /*
2  * Copyright (C) 2004, OGAWA Hirofumi
3  * Released under GPL v2.
4  */
5 
6 #include <linux/module.h>
7 #include <linux/fs.h>
8 #include <linux/msdos_fs.h>
9 
10 struct fatent_operations {
11 	void (*ent_blocknr)(struct super_block *, int, int *, sector_t *);
12 	void (*ent_set_ptr)(struct fat_entry *, int);
13 	int (*ent_bread)(struct super_block *, struct fat_entry *,
14 			 int, sector_t);
15 	int (*ent_get)(struct fat_entry *);
16 	void (*ent_put)(struct fat_entry *, int);
17 	int (*ent_next)(struct fat_entry *);
18 };
19 
20 static void fat12_ent_blocknr(struct super_block *sb, int entry,
21 			      int *offset, sector_t *blocknr)
22 {
23 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
24 	int bytes = entry + (entry >> 1);
25 	WARN_ON(entry < FAT_START_ENT || sbi->max_cluster <= entry);
26 	*offset = bytes & (sb->s_blocksize - 1);
27 	*blocknr = sbi->fat_start + (bytes >> sb->s_blocksize_bits);
28 }
29 
30 static void fat_ent_blocknr(struct super_block *sb, int entry,
31 			    int *offset, sector_t *blocknr)
32 {
33 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
34 	int bytes = (entry << sbi->fatent_shift);
35 	WARN_ON(entry < FAT_START_ENT || sbi->max_cluster <= entry);
36 	*offset = bytes & (sb->s_blocksize - 1);
37 	*blocknr = sbi->fat_start + (bytes >> sb->s_blocksize_bits);
38 }
39 
40 static void fat12_ent_set_ptr(struct fat_entry *fatent, int offset)
41 {
42 	struct buffer_head **bhs = fatent->bhs;
43 	if (fatent->nr_bhs == 1) {
44 		WARN_ON(offset >= (bhs[0]->b_size - 1));
45 		fatent->u.ent12_p[0] = bhs[0]->b_data + offset;
46 		fatent->u.ent12_p[1] = bhs[0]->b_data + (offset + 1);
47 	} else {
48 		WARN_ON(offset != (bhs[0]->b_size - 1));
49 		fatent->u.ent12_p[0] = bhs[0]->b_data + offset;
50 		fatent->u.ent12_p[1] = bhs[1]->b_data;
51 	}
52 }
53 
54 static void fat16_ent_set_ptr(struct fat_entry *fatent, int offset)
55 {
56 	WARN_ON(offset & (2 - 1));
57 	fatent->u.ent16_p = (__le16 *)(fatent->bhs[0]->b_data + offset);
58 }
59 
60 static void fat32_ent_set_ptr(struct fat_entry *fatent, int offset)
61 {
62 	WARN_ON(offset & (4 - 1));
63 	fatent->u.ent32_p = (__le32 *)(fatent->bhs[0]->b_data + offset);
64 }
65 
66 static int fat12_ent_bread(struct super_block *sb, struct fat_entry *fatent,
67 			   int offset, sector_t blocknr)
68 {
69 	struct buffer_head **bhs = fatent->bhs;
70 
71 	WARN_ON(blocknr < MSDOS_SB(sb)->fat_start);
72 	bhs[0] = sb_bread(sb, blocknr);
73 	if (!bhs[0])
74 		goto err;
75 
76 	if ((offset + 1) < sb->s_blocksize)
77 		fatent->nr_bhs = 1;
78 	else {
79 		/* This entry is block boundary, it needs the next block */
80 		blocknr++;
81 		bhs[1] = sb_bread(sb, blocknr);
82 		if (!bhs[1])
83 			goto err_brelse;
84 		fatent->nr_bhs = 2;
85 	}
86 	fat12_ent_set_ptr(fatent, offset);
87 	return 0;
88 
89 err_brelse:
90 	brelse(bhs[0]);
91 err:
92 	printk(KERN_ERR "FAT: FAT read failed (blocknr %llu)\n",
93 	       (unsigned long long)blocknr);
94 	return -EIO;
95 }
96 
97 static int fat_ent_bread(struct super_block *sb, struct fat_entry *fatent,
98 			 int offset, sector_t blocknr)
99 {
100 	struct fatent_operations *ops = MSDOS_SB(sb)->fatent_ops;
101 
102 	WARN_ON(blocknr < MSDOS_SB(sb)->fat_start);
103 	fatent->bhs[0] = sb_bread(sb, blocknr);
104 	if (!fatent->bhs[0]) {
105 		printk(KERN_ERR "FAT: FAT read failed (blocknr %llu)\n",
106 		       (unsigned long long)blocknr);
107 		return -EIO;
108 	}
109 	fatent->nr_bhs = 1;
110 	ops->ent_set_ptr(fatent, offset);
111 	return 0;
112 }
113 
114 static int fat12_ent_get(struct fat_entry *fatent)
115 {
116 	u8 **ent12_p = fatent->u.ent12_p;
117 	int next;
118 
119 	if (fatent->entry & 1)
120 		next = (*ent12_p[0] >> 4) | (*ent12_p[1] << 4);
121 	else
122 		next = (*ent12_p[1] << 8) | *ent12_p[0];
123 	next &= 0x0fff;
124 	if (next >= BAD_FAT12)
125 		next = FAT_ENT_EOF;
126 	return next;
127 }
128 
129 static int fat16_ent_get(struct fat_entry *fatent)
130 {
131 	int next = le16_to_cpu(*fatent->u.ent16_p);
132 	WARN_ON((unsigned long)fatent->u.ent16_p & (2 - 1));
133 	if (next >= BAD_FAT16)
134 		next = FAT_ENT_EOF;
135 	return next;
136 }
137 
138 static int fat32_ent_get(struct fat_entry *fatent)
139 {
140 	int next = le32_to_cpu(*fatent->u.ent32_p) & 0x0fffffff;
141 	WARN_ON((unsigned long)fatent->u.ent32_p & (4 - 1));
142 	if (next >= BAD_FAT32)
143 		next = FAT_ENT_EOF;
144 	return next;
145 }
146 
147 static void fat12_ent_put(struct fat_entry *fatent, int new)
148 {
149 	u8 **ent12_p = fatent->u.ent12_p;
150 
151 	if (new == FAT_ENT_EOF)
152 		new = EOF_FAT12;
153 
154 	if (fatent->entry & 1) {
155 		*ent12_p[0] = (new << 4) | (*ent12_p[0] & 0x0f);
156 		*ent12_p[1] = new >> 4;
157 	} else {
158 		*ent12_p[0] = new & 0xff;
159 		*ent12_p[1] = (*ent12_p[1] & 0xf0) | (new >> 8);
160 	}
161 
162 	mark_buffer_dirty(fatent->bhs[0]);
163 	if (fatent->nr_bhs == 2)
164 		mark_buffer_dirty(fatent->bhs[1]);
165 }
166 
167 static void fat16_ent_put(struct fat_entry *fatent, int new)
168 {
169 	if (new == FAT_ENT_EOF)
170 		new = EOF_FAT16;
171 
172 	*fatent->u.ent16_p = cpu_to_le16(new);
173 	mark_buffer_dirty(fatent->bhs[0]);
174 }
175 
176 static void fat32_ent_put(struct fat_entry *fatent, int new)
177 {
178 	if (new == FAT_ENT_EOF)
179 		new = EOF_FAT32;
180 
181 	WARN_ON(new & 0xf0000000);
182 	new |= le32_to_cpu(*fatent->u.ent32_p) & ~0x0fffffff;
183 	*fatent->u.ent32_p = cpu_to_le32(new);
184 	mark_buffer_dirty(fatent->bhs[0]);
185 }
186 
187 static int fat12_ent_next(struct fat_entry *fatent)
188 {
189 	u8 **ent12_p = fatent->u.ent12_p;
190 	struct buffer_head **bhs = fatent->bhs;
191 	u8 *nextp = ent12_p[1] + 1 + (fatent->entry & 1);
192 
193 	fatent->entry++;
194 	if (fatent->nr_bhs == 1) {
195 		WARN_ON(ent12_p[0] > (u8 *)(bhs[0]->b_data + (bhs[0]->b_size - 2)));
196 		WARN_ON(ent12_p[1] > (u8 *)(bhs[0]->b_data + (bhs[0]->b_size - 1)));
197 		if (nextp < (u8 *)(bhs[0]->b_data + (bhs[0]->b_size - 1))) {
198 			ent12_p[0] = nextp - 1;
199 			ent12_p[1] = nextp;
200 			return 1;
201 		}
202 	} else {
203 		WARN_ON(ent12_p[0] != (u8 *)(bhs[0]->b_data + (bhs[0]->b_size - 1)));
204 		WARN_ON(ent12_p[1] != (u8 *)bhs[1]->b_data);
205 		ent12_p[0] = nextp - 1;
206 		ent12_p[1] = nextp;
207 		brelse(bhs[0]);
208 		bhs[0] = bhs[1];
209 		fatent->nr_bhs = 1;
210 		return 1;
211 	}
212 	ent12_p[0] = NULL;
213 	ent12_p[1] = NULL;
214 	return 0;
215 }
216 
217 static int fat16_ent_next(struct fat_entry *fatent)
218 {
219 	const struct buffer_head *bh = fatent->bhs[0];
220 	fatent->entry++;
221 	if (fatent->u.ent16_p < (__le16 *)(bh->b_data + (bh->b_size - 2))) {
222 		fatent->u.ent16_p++;
223 		return 1;
224 	}
225 	fatent->u.ent16_p = NULL;
226 	return 0;
227 }
228 
229 static int fat32_ent_next(struct fat_entry *fatent)
230 {
231 	const struct buffer_head *bh = fatent->bhs[0];
232 	fatent->entry++;
233 	if (fatent->u.ent32_p < (__le32 *)(bh->b_data + (bh->b_size - 4))) {
234 		fatent->u.ent32_p++;
235 		return 1;
236 	}
237 	fatent->u.ent32_p = NULL;
238 	return 0;
239 }
240 
241 static struct fatent_operations fat12_ops = {
242 	.ent_blocknr	= fat12_ent_blocknr,
243 	.ent_set_ptr	= fat12_ent_set_ptr,
244 	.ent_bread	= fat12_ent_bread,
245 	.ent_get	= fat12_ent_get,
246 	.ent_put	= fat12_ent_put,
247 	.ent_next	= fat12_ent_next,
248 };
249 
250 static struct fatent_operations fat16_ops = {
251 	.ent_blocknr	= fat_ent_blocknr,
252 	.ent_set_ptr	= fat16_ent_set_ptr,
253 	.ent_bread	= fat_ent_bread,
254 	.ent_get	= fat16_ent_get,
255 	.ent_put	= fat16_ent_put,
256 	.ent_next	= fat16_ent_next,
257 };
258 
259 static struct fatent_operations fat32_ops = {
260 	.ent_blocknr	= fat_ent_blocknr,
261 	.ent_set_ptr	= fat32_ent_set_ptr,
262 	.ent_bread	= fat_ent_bread,
263 	.ent_get	= fat32_ent_get,
264 	.ent_put	= fat32_ent_put,
265 	.ent_next	= fat32_ent_next,
266 };
267 
268 static inline void lock_fat(struct msdos_sb_info *sbi)
269 {
270 	down(&sbi->fat_lock);
271 }
272 
273 static inline void unlock_fat(struct msdos_sb_info *sbi)
274 {
275 	up(&sbi->fat_lock);
276 }
277 
278 void fat_ent_access_init(struct super_block *sb)
279 {
280 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
281 
282 	init_MUTEX(&sbi->fat_lock);
283 
284 	switch (sbi->fat_bits) {
285 	case 32:
286 		sbi->fatent_shift = 2;
287 		sbi->fatent_ops = &fat32_ops;
288 		break;
289 	case 16:
290 		sbi->fatent_shift = 1;
291 		sbi->fatent_ops = &fat16_ops;
292 		break;
293 	case 12:
294 		sbi->fatent_shift = -1;
295 		sbi->fatent_ops = &fat12_ops;
296 		break;
297 	}
298 }
299 
300 static inline int fat_ent_update_ptr(struct super_block *sb,
301 				     struct fat_entry *fatent,
302 				     int offset, sector_t blocknr)
303 {
304 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
305 	struct fatent_operations *ops = sbi->fatent_ops;
306 	struct buffer_head **bhs = fatent->bhs;
307 
308 	/* Is this fatent's blocks including this entry? */
309 	if (!fatent->nr_bhs || bhs[0]->b_blocknr != blocknr)
310 		return 0;
311 	/* Does this entry need the next block? */
312 	if (sbi->fat_bits == 12 && (offset + 1) >= sb->s_blocksize) {
313 		if (fatent->nr_bhs != 2 || bhs[1]->b_blocknr != (blocknr + 1))
314 			return 0;
315 	}
316 	ops->ent_set_ptr(fatent, offset);
317 	return 1;
318 }
319 
320 int fat_ent_read(struct inode *inode, struct fat_entry *fatent, int entry)
321 {
322 	struct super_block *sb = inode->i_sb;
323 	struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);
324 	struct fatent_operations *ops = sbi->fatent_ops;
325 	int err, offset;
326 	sector_t blocknr;
327 
328 	if (entry < FAT_START_ENT || sbi->max_cluster <= entry) {
329 		fatent_brelse(fatent);
330 		fat_fs_panic(sb, "invalid access to FAT (entry 0x%08x)", entry);
331 		return -EIO;
332 	}
333 
334 	fatent_set_entry(fatent, entry);
335 	ops->ent_blocknr(sb, entry, &offset, &blocknr);
336 
337 	if (!fat_ent_update_ptr(sb, fatent, offset, blocknr)) {
338 		fatent_brelse(fatent);
339 		err = ops->ent_bread(sb, fatent, offset, blocknr);
340 		if (err)
341 			return err;
342 	}
343 	return ops->ent_get(fatent);
344 }
345 
346 /* FIXME: We can write the blocks as more big chunk. */
347 static int fat_mirror_bhs(struct super_block *sb, struct buffer_head **bhs,
348 			  int nr_bhs)
349 {
350 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
351 	struct buffer_head *c_bh;
352 	int err, n, copy;
353 
354 	err = 0;
355 	for (copy = 1; copy < sbi->fats; copy++) {
356 		sector_t backup_fat = sbi->fat_length * copy;
357 
358 		for (n = 0; n < nr_bhs; n++) {
359 			c_bh = sb_getblk(sb, backup_fat + bhs[n]->b_blocknr);
360 			if (!c_bh) {
361 				err = -ENOMEM;
362 				goto error;
363 			}
364 			memcpy(c_bh->b_data, bhs[n]->b_data, sb->s_blocksize);
365 			set_buffer_uptodate(c_bh);
366 			mark_buffer_dirty(c_bh);
367 			if (sb->s_flags & MS_SYNCHRONOUS)
368 				err = sync_dirty_buffer(c_bh);
369 			brelse(c_bh);
370 			if (err)
371 				goto error;
372 		}
373 	}
374 error:
375 	return err;
376 }
377 
378 int fat_ent_write(struct inode *inode, struct fat_entry *fatent,
379 		  int new, int wait)
380 {
381 	struct super_block *sb = inode->i_sb;
382 	struct fatent_operations *ops = MSDOS_SB(sb)->fatent_ops;
383 	int err;
384 
385 	ops->ent_put(fatent, new);
386 	if (wait) {
387 		err = fat_sync_bhs(fatent->bhs, fatent->nr_bhs);
388 		if (err)
389 			return err;
390 	}
391 	return fat_mirror_bhs(sb, fatent->bhs, fatent->nr_bhs);
392 }
393 
394 static inline int fat_ent_next(struct msdos_sb_info *sbi,
395 			       struct fat_entry *fatent)
396 {
397 	if (sbi->fatent_ops->ent_next(fatent)) {
398 		if (fatent->entry < sbi->max_cluster)
399 			return 1;
400 	}
401 	return 0;
402 }
403 
404 static inline int fat_ent_read_block(struct super_block *sb,
405 				     struct fat_entry *fatent)
406 {
407 	struct fatent_operations *ops = MSDOS_SB(sb)->fatent_ops;
408 	sector_t blocknr;
409 	int offset;
410 
411 	fatent_brelse(fatent);
412 	ops->ent_blocknr(sb, fatent->entry, &offset, &blocknr);
413 	return ops->ent_bread(sb, fatent, offset, blocknr);
414 }
415 
416 static void fat_collect_bhs(struct buffer_head **bhs, int *nr_bhs,
417 			    struct fat_entry *fatent)
418 {
419 	int n, i;
420 
421 	for (n = 0; n < fatent->nr_bhs; n++) {
422 		for (i = 0; i < *nr_bhs; i++) {
423 			if (fatent->bhs[n] == bhs[i])
424 				break;
425 		}
426 		if (i == *nr_bhs) {
427 			get_bh(fatent->bhs[n]);
428 			bhs[i] = fatent->bhs[n];
429 			(*nr_bhs)++;
430 		}
431 	}
432 }
433 
434 int fat_alloc_clusters(struct inode *inode, int *cluster, int nr_cluster)
435 {
436 	struct super_block *sb = inode->i_sb;
437 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
438 	struct fatent_operations *ops = sbi->fatent_ops;
439 	struct fat_entry fatent, prev_ent;
440 	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
441 	int i, count, err, nr_bhs, idx_clus;
442 
443 	BUG_ON(nr_cluster > (MAX_BUF_PER_PAGE / 2));	/* fixed limit */
444 
445 	lock_fat(sbi);
446 	if (sbi->free_clusters != -1 && sbi->free_clusters < nr_cluster) {
447 		unlock_fat(sbi);
448 		return -ENOSPC;
449 	}
450 
451 	err = nr_bhs = idx_clus = 0;
452 	count = FAT_START_ENT;
453 	fatent_init(&prev_ent);
454 	fatent_init(&fatent);
455 	fatent_set_entry(&fatent, sbi->prev_free + 1);
456 	while (count < sbi->max_cluster) {
457 		if (fatent.entry >= sbi->max_cluster)
458 			fatent.entry = FAT_START_ENT;
459 		fatent_set_entry(&fatent, fatent.entry);
460 		err = fat_ent_read_block(sb, &fatent);
461 		if (err)
462 			goto out;
463 
464 		/* Find the free entries in a block */
465 		do {
466 			if (ops->ent_get(&fatent) == FAT_ENT_FREE) {
467 				int entry = fatent.entry;
468 
469 				/* make the cluster chain */
470 				ops->ent_put(&fatent, FAT_ENT_EOF);
471 				if (prev_ent.nr_bhs)
472 					ops->ent_put(&prev_ent, entry);
473 
474 				fat_collect_bhs(bhs, &nr_bhs, &fatent);
475 
476 				sbi->prev_free = entry;
477 				if (sbi->free_clusters != -1)
478 					sbi->free_clusters--;
479 
480 				cluster[idx_clus] = entry;
481 				idx_clus++;
482 				if (idx_clus == nr_cluster)
483 					goto out;
484 
485 				/*
486 				 * fat_collect_bhs() gets ref-count of bhs,
487 				 * so we can still use the prev_ent.
488 				 */
489 				prev_ent = fatent;
490 			}
491 			count++;
492 			if (count == sbi->max_cluster)
493 				break;
494 		} while (fat_ent_next(sbi, &fatent));
495 	}
496 
497 	/* Couldn't allocate the free entries */
498 	sbi->free_clusters = 0;
499 	err = -ENOSPC;
500 
501 out:
502 	unlock_fat(sbi);
503 	fatent_brelse(&fatent);
504 	if (!err) {
505 		if (inode_needs_sync(inode))
506 			err = fat_sync_bhs(bhs, nr_bhs);
507 		if (!err)
508 			err = fat_mirror_bhs(sb, bhs, nr_bhs);
509 	}
510 	for (i = 0; i < nr_bhs; i++)
511 		brelse(bhs[i]);
512 	fat_clusters_flush(sb);
513 
514 	if (err && idx_clus)
515 		fat_free_clusters(inode, cluster[0]);
516 
517 	return err;
518 }
519 
520 int fat_free_clusters(struct inode *inode, int cluster)
521 {
522 	struct super_block *sb = inode->i_sb;
523 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
524 	struct fatent_operations *ops = sbi->fatent_ops;
525 	struct fat_entry fatent;
526 	struct buffer_head *bhs[MAX_BUF_PER_PAGE];
527 	int i, err, nr_bhs;
528 
529 	nr_bhs = 0;
530 	fatent_init(&fatent);
531 	lock_fat(sbi);
532 	do {
533 		cluster = fat_ent_read(inode, &fatent, cluster);
534 		if (cluster < 0) {
535 			err = cluster;
536 			goto error;
537 		} else if (cluster == FAT_ENT_FREE) {
538 			fat_fs_panic(sb, "%s: deleting FAT entry beyond EOF",
539 				     __FUNCTION__);
540 			err = -EIO;
541 			goto error;
542 		}
543 
544 		ops->ent_put(&fatent, FAT_ENT_FREE);
545 		if (sbi->free_clusters != -1)
546 			sbi->free_clusters++;
547 
548 		if (nr_bhs + fatent.nr_bhs > MAX_BUF_PER_PAGE) {
549 			if (sb->s_flags & MS_SYNCHRONOUS) {
550 				err = fat_sync_bhs(bhs, nr_bhs);
551 				if (err)
552 					goto error;
553 			}
554 			err = fat_mirror_bhs(sb, bhs, nr_bhs);
555 			if (err)
556 				goto error;
557 			for (i = 0; i < nr_bhs; i++)
558 				brelse(bhs[i]);
559 			nr_bhs = 0;
560 		}
561 		fat_collect_bhs(bhs, &nr_bhs, &fatent);
562 	} while (cluster != FAT_ENT_EOF);
563 
564 	if (sb->s_flags & MS_SYNCHRONOUS) {
565 		err = fat_sync_bhs(bhs, nr_bhs);
566 		if (err)
567 			goto error;
568 	}
569 	err = fat_mirror_bhs(sb, bhs, nr_bhs);
570 error:
571 	fatent_brelse(&fatent);
572 	for (i = 0; i < nr_bhs; i++)
573 		brelse(bhs[i]);
574 	unlock_fat(sbi);
575 
576 	fat_clusters_flush(sb);
577 
578 	return err;
579 }
580 
581 EXPORT_SYMBOL(fat_free_clusters);
582 
583 int fat_count_free_clusters(struct super_block *sb)
584 {
585 	struct msdos_sb_info *sbi = MSDOS_SB(sb);
586 	struct fatent_operations *ops = sbi->fatent_ops;
587 	struct fat_entry fatent;
588 	int err = 0, free;
589 
590 	lock_fat(sbi);
591 	if (sbi->free_clusters != -1)
592 		goto out;
593 
594 	free = 0;
595 	fatent_init(&fatent);
596 	fatent_set_entry(&fatent, FAT_START_ENT);
597 	while (fatent.entry < sbi->max_cluster) {
598 		err = fat_ent_read_block(sb, &fatent);
599 		if (err)
600 			goto out;
601 
602 		do {
603 			if (ops->ent_get(&fatent) == FAT_ENT_FREE)
604 				free++;
605 		} while (fat_ent_next(sbi, &fatent));
606 	}
607 	sbi->free_clusters = free;
608 	fatent_brelse(&fatent);
609 out:
610 	unlock_fat(sbi);
611 	return err;
612 }
613