1/*
2	Copyright 1999-2001, Be Incorporated.   All Rights Reserved.
3	This file may be used under the terms of the Be Sample Code License.
4*/
5
6
7#include "fat.h"
8
9#include <stdlib.h>
10#include <string.h>
11
12#include <fs_cache.h>
13#include <ByteOrder.h>
14#include <KernelExport.h>
15
16#include "dosfs.h"
17#include "file.h"
18#include "util.h"
19#include "vcache.h"
20
21
22#define END_FAT_ENTRY 0x0fffffff
23#define BAD_FAT_ENTRY 0x0ffffff1
24
25#define DPRINTF(a,b) if (debug_fat > (a)) dprintf b
26
27
28static status_t
29mirror_fats(nspace *vol, uint32 sector, uint8 *buffer)
30{
31	uint32 i;
32
33	if (!vol->fat_mirrored)
34		return B_OK;
35
36	sector -= vol->active_fat * vol->sectors_per_fat;
37
38	for (i = 0; i < vol->fat_count; i++) {
39		char *blockData;
40		if (i == vol->active_fat)
41			continue;
42
43		blockData = block_cache_get_writable_etc(vol->fBlockCache, sector
44			+ i * vol->sectors_per_fat, 0, 1, -1);
45		memcpy(blockData, buffer, vol->bytes_per_sector);
46		block_cache_put(vol->fBlockCache, sector + i * vol->sectors_per_fat);
47	}
48
49	return B_OK;
50}
51
52
53static int32
54_count_free_clusters_fat32(nspace *vol)
55{
56	int32 count = 0;
57	const uint8 *block;
58	uint32 fat_sector;
59	uint32 i;
60	uint32 cur_sector;
61
62	cur_sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat;
63
64	for (fat_sector = 0; fat_sector < vol->sectors_per_fat; fat_sector++) {
65		block = (uint8 *)block_cache_get(vol->fBlockCache, cur_sector);
66		if(block == NULL)
67			return B_IO_ERROR;
68
69		for (i = 0; i < vol->bytes_per_sector; i += sizeof(uint32)) {
70			uint32 val = read32(block, i);
71			if ((val & 0x0fffffff) == 0)
72				count++;
73		}
74
75		block_cache_put(vol->fBlockCache, cur_sector);
76		cur_sector++;
77	}
78
79	return count;
80}
81
82// count free: no parameters. returns int32
83// get_entry: cluster #. returns int32 entry/status
84// set_entry: cluster #, value. returns int32 status
85// allocate: # clusters in N, returns int32 status/starting cluster
86
87enum {
88	_IOCTL_COUNT_FREE_,
89	_IOCTL_GET_ENTRY_,
90	_IOCTL_SET_ENTRY_,
91	_IOCTL_ALLOCATE_N_ENTRIES_
92};
93
94static int32
95_fat_ioctl_(nspace *vol, uint32 action, uint32 cluster, int32 N)
96{
97	int32 result = 0;
98	uint32 n = 0, first = 0, last = 0;
99	uint32 i;
100	uint32 sector;
101	uint32 offset, value = 0; /* quiet warning */
102	uint8 *block1, *block2 = NULL; /* quiet warning */
103	bool readOnly
104		= action != _IOCTL_SET_ENTRY_ && action != _IOCTL_ALLOCATE_N_ENTRIES_;
105
106	// mark end of chain for allocations
107	uint32 endOfChainMarker = (action == _IOCTL_SET_ENTRY_) ? N : 0x0fffffff;
108
109	ASSERT(action >= _IOCTL_COUNT_FREE_
110		&& action <= _IOCTL_ALLOCATE_N_ENTRIES_);
111
112	DPRINTF(3, ("_fat_ioctl_: action %lx, cluster %ld, N %ld\n", action,
113		cluster, N));
114
115	if (action == _IOCTL_COUNT_FREE_) {
116		if(vol->fat_bits == 32)
117			// use a optimized version of the cluster counting algorithms
118			return _count_free_clusters_fat32(vol);
119		else
120			cluster = 2;
121	}
122
123	if (action == _IOCTL_ALLOCATE_N_ENTRIES_)
124		cluster = vol->last_allocated;
125
126	if (action != _IOCTL_COUNT_FREE_) {
127		if (!IS_DATA_CLUSTER(cluster)) {
128			DPRINTF(0, ("_fat_ioctl_ called with invalid cluster (%ld)\n",
129				cluster));
130			return B_BAD_VALUE;
131		}
132	}
133
134	offset = cluster * vol->fat_bits / 8;
135	sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat +
136		offset / vol->bytes_per_sector;
137	offset %= vol->bytes_per_sector;
138
139	if (readOnly) {
140		block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector);
141	} else {
142		block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache, sector,
143			-1);
144	}
145
146	if (block1 == NULL) {
147		DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n", sector));
148		return B_IO_ERROR;
149	}
150
151	for (i = 0; i < vol->total_clusters; i++) {
152		ASSERT(IS_DATA_CLUSTER(cluster));
153		ASSERT(offset == ((cluster * vol->fat_bits / 8)
154			% vol->bytes_per_sector));
155
156		if (vol->fat_bits == 12) {
157			if (offset == vol->bytes_per_sector - 1) {
158				if (readOnly) {
159					block2 = (uint8 *)block_cache_get(vol->fBlockCache,
160						++sector);
161				} else {
162					block2 = (uint8 *)block_cache_get_writable(vol->fBlockCache,
163						++sector, -1);
164				}
165
166				if (block2 == NULL) {
167					DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n",
168						sector));
169					result = B_IO_ERROR;
170					sector--;
171					goto bi;
172				}
173			}
174
175			if (action != _IOCTL_SET_ENTRY_) {
176				if (offset == vol->bytes_per_sector - 1)
177					value = block1[offset] + 0x100 * block2[0];
178				else
179					value = block1[offset] + 0x100 * block1[offset + 1];
180
181				if (cluster & 1)
182					value >>= 4;
183				else
184					value &= 0xfff;
185
186				if (value > 0xff0)
187					value |= 0x0ffff000;
188			}
189
190			if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0))
191				|| action == _IOCTL_SET_ENTRY_) {
192				uint32 andmask, ormask;
193				if (cluster & 1) {
194					ormask = (endOfChainMarker & 0xfff) << 4;
195					andmask = 0xf;
196				} else {
197					ormask = endOfChainMarker & 0xfff;
198					andmask = 0xf000;
199				}
200
201				block1[offset] &= (andmask & 0xff);
202				block1[offset] |= (ormask & 0xff);
203				if (offset == vol->bytes_per_sector - 1) {
204					mirror_fats(vol, sector - 1, block1);
205					block2[0] &= (andmask >> 8);
206					block2[0] |= (ormask >> 8);
207				} else {
208					block1[offset + 1] &= (andmask >> 8);
209					block1[offset + 1] |= (ormask >> 8);
210				}
211			}
212
213			if (offset == vol->bytes_per_sector - 1) {
214				offset = (cluster & 1) ? 1 : 0;
215				block_cache_put(vol->fBlockCache, sector - 1);
216				block1 = block2;
217			} else
218				offset += (cluster & 1) ? 2 : 1;
219
220		} else if (vol->fat_bits == 16) {
221			if (action != _IOCTL_SET_ENTRY_) {
222				value = read16(block1, offset);
223				if (value > 0xfff0)
224					value |= 0x0fff0000;
225			}
226
227			if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0))
228				|| action == _IOCTL_SET_ENTRY_) {
229				*(uint16 *)&block1[offset]
230					= B_HOST_TO_LENDIAN_INT16(endOfChainMarker);
231			}
232
233			offset += 2;
234		} else if (vol->fat_bits == 32) {
235			if (action != _IOCTL_SET_ENTRY_)
236				value = read32(block1, offset) & 0x0fffffff;
237
238			if (((action == _IOCTL_ALLOCATE_N_ENTRIES_) && (value == 0))
239				|| action == _IOCTL_SET_ENTRY_) {
240				ASSERT((endOfChainMarker & 0xf0000000) == 0);
241				*(uint32 *)&block1[offset]
242					= B_HOST_TO_LENDIAN_INT32(endOfChainMarker);
243			}
244
245			offset += 4;
246		} else
247			ASSERT(0);
248
249		if (action == _IOCTL_COUNT_FREE_) {
250			if (value == 0)
251				result++;
252		} else if (action == _IOCTL_GET_ENTRY_) {
253			result = value;
254			goto bi;
255		} else if (action == _IOCTL_SET_ENTRY_) {
256			mirror_fats(vol, sector, block1);
257			goto bi;
258		} else if (action == _IOCTL_ALLOCATE_N_ENTRIES_ && value == 0) {
259			vol->free_clusters--;
260			mirror_fats(vol, sector, block1);
261
262			if (n == 0) {
263				ASSERT(first == 0);
264				first = last = cluster;
265			} else {
266				ASSERT(IS_DATA_CLUSTER(first));
267				ASSERT(IS_DATA_CLUSTER(last));
268				// set last cluster to point to us
269
270				result = _fat_ioctl_(vol, _IOCTL_SET_ENTRY_, last, cluster);
271				if (result < 0) {
272					ASSERT(0);
273					goto bi;
274				}
275
276				last = cluster;
277			}
278
279			if (++n == N)
280				goto bi;
281		}
282
283		// iterate cluster and sector if needed
284		if (++cluster == vol->total_clusters + 2) {
285			block_cache_put(vol->fBlockCache, sector);
286
287			cluster = 2;
288			offset = cluster * vol->fat_bits / 8;
289			sector = vol->reserved_sectors + vol->active_fat
290				* vol->sectors_per_fat;
291
292			if (readOnly)
293				block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector);
294			else {
295				block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache,
296					sector, -1);
297			}
298		}
299
300		if (offset >= vol->bytes_per_sector) {
301			block_cache_put(vol->fBlockCache, sector);
302
303			sector++;
304			offset -= vol->bytes_per_sector;
305			ASSERT(sector < vol->reserved_sectors + (vol->active_fat + 1)
306				* vol->sectors_per_fat);
307
308			if (readOnly)
309				block1 = (uint8 *)block_cache_get(vol->fBlockCache, sector);
310			else {
311				block1 = (uint8 *)block_cache_get_writable(vol->fBlockCache,
312					sector, -1);
313			}
314		}
315
316		if (block1 == NULL) {
317			DPRINTF(0, ("_fat_ioctl_: error reading fat (sector %ld)\n", sector));
318			result = B_IO_ERROR;
319			goto bi;
320		}
321	}
322
323bi:
324	if (block1 != NULL)
325		block_cache_put(vol->fBlockCache, sector);
326
327	if (action == _IOCTL_ALLOCATE_N_ENTRIES_) {
328		if (result < 0) {
329			DPRINTF(0, ("pooh. there is a problem. clearing chain (%ld)\n",
330				first));
331			if (first != 0)
332				clear_fat_chain(vol, first);
333		} else if (n != N) {
334			DPRINTF(0, ("not enough free entries (%ld/%ld found)\n", n, N));
335			if (first != 0)
336				clear_fat_chain(vol, first);
337			result = B_DEVICE_FULL;
338		} else if (result == 0) {
339			vol->last_allocated = cluster;
340			result = first;
341			ASSERT(IS_DATA_CLUSTER(first));
342		}
343	}
344
345	if (result < B_OK) {
346		DPRINTF(0, ("_fat_ioctl_ error: action = %lx cluster = %ld N = %ld "
347			"(%s)\n", action, cluster, N, strerror(result)));
348	}
349
350	return result;
351}
352
353
354int32
355count_free_clusters(nspace *vol)
356{
357	return _fat_ioctl_(vol, _IOCTL_COUNT_FREE_, 0, 0);
358}
359
360
361static int32
362get_fat_entry(nspace *vol, uint32 cluster)
363{
364	int32 value = _fat_ioctl_(vol, _IOCTL_GET_ENTRY_, cluster, 0);
365
366	if (value < 0)
367		return value;
368
369	if (value == 0 || IS_DATA_CLUSTER(value))
370		return value;
371
372	if (value > 0x0ffffff7)
373		return END_FAT_ENTRY;
374
375	if (value > 0x0ffffff0)
376		return BAD_FAT_ENTRY;
377
378	DPRINTF(0, ("invalid fat entry: 0x%08lx\n", value));
379	return BAD_FAT_ENTRY;
380}
381
382
383static status_t
384set_fat_entry(nspace *vol, uint32 cluster, int32 value)
385{
386	return _fat_ioctl_(vol, _IOCTL_SET_ENTRY_, cluster, value);
387}
388
389
390//! Traverse n fat entries
391int32
392get_nth_fat_entry(nspace *vol, int32 cluster, uint32 n)
393{
394	while (n--) {
395		cluster = get_fat_entry(vol, cluster);
396
397		if (!IS_DATA_CLUSTER(cluster))
398			break;
399	}
400
401	ASSERT(cluster != 0);
402	return cluster;
403}
404
405
406// count number of clusters in fat chain starting at given cluster
407// should only be used for calculating directory sizes because it doesn't
408// return proper error codes
409uint32
410count_clusters(nspace *vol, int32 cluster)
411{
412	int32 count = 0;
413
414	DPRINTF(2, ("count_clusters %ld\n", cluster));
415
416	// not intended for use on root directory
417	if (!IS_DATA_CLUSTER(cluster)) {
418		DPRINTF(0, ("count_clusters called on invalid cluster (%ld)\n",
419			cluster));
420		return 0;
421	}
422
423	while (IS_DATA_CLUSTER(cluster)) {
424		count++;
425
426		// break out of circular fat chains in a sketchy manner
427		if (count == vol->total_clusters)
428			return 0;
429
430		cluster = get_fat_entry(vol, cluster);
431	}
432
433	DPRINTF(2, ("count_clusters %ld = %ld\n", cluster, count));
434
435	if (cluster == END_FAT_ENTRY)
436		return count;
437
438	dprintf("cluster = %ld\n", cluster);
439	ASSERT(0);
440	return 0;
441}
442
443
444status_t
445clear_fat_chain(nspace *vol, uint32 cluster)
446{
447	int32 c;
448	status_t result;
449
450	if (!IS_DATA_CLUSTER(cluster)) {
451		DPRINTF(0, ("clear_fat_chain called on invalid cluster (%ld)\n",
452			cluster));
453		return B_BAD_VALUE;
454	}
455
456	ASSERT(count_clusters(vol, cluster) != 0);
457
458	DPRINTF(2, ("clearing fat chain: %ld", cluster));
459	while (IS_DATA_CLUSTER(cluster)) {
460		if ((c = get_fat_entry(vol, cluster)) < 0) {
461			DPRINTF(0, ("clear_fat_chain: error clearing fat entry for cluster "
462				"%ld (%s)\n", cluster, strerror(c)));
463			return c;
464		}
465
466		if ((result = set_fat_entry(vol, cluster, 0)) != B_OK) {
467			DPRINTF(0, ("clear_fat_chain: error clearing fat entry for cluster "
468				"%ld (%s)\n", cluster, strerror(result)));
469			return result;
470		}
471
472		vol->free_clusters++;
473		cluster = c;
474		DPRINTF(2, (", %ld", cluster));
475	}
476	DPRINTF(2, ("\n"));
477
478	if (cluster != END_FAT_ENTRY) {
479		dprintf("clear_fat_chain: fat chain terminated improperly with %ld\n",
480			cluster);
481	}
482
483	return 0;
484}
485
486
487status_t
488allocate_n_fat_entries(nspace *vol, int32 n, int32 *start)
489{
490	int32 c;
491
492	ASSERT(n > 0);
493
494	DPRINTF(2, ("allocating %ld fat entries\n", n));
495
496	c = _fat_ioctl_(vol, _IOCTL_ALLOCATE_N_ENTRIES_, 0, n);
497	if (c < 0)
498		return c;
499
500	ASSERT(IS_DATA_CLUSTER(c));
501	ASSERT(count_clusters(vol, c) == n);
502
503	DPRINTF(2, ("allocated %ld fat entries at %ld\n", n, c));
504
505	*start = c;
506	return 0;
507}
508
509
510status_t
511set_fat_chain_length(nspace *vol, vnode *node, uint32 clusters)
512{
513	status_t result;
514	int32 i, c, n;
515
516	DPRINTF(1, ("set_fat_chain_length: %Lx to %ld clusters (%ld)\n", node->vnid,
517		clusters, node->cluster));
518
519	if (IS_FIXED_ROOT(node->cluster)
520		|| (!IS_DATA_CLUSTER(node->cluster) && (node->cluster != 0))) {
521		DPRINTF(0, ("set_fat_chain_length called on invalid cluster (%ld)\n",
522			node->cluster));
523		return B_BAD_VALUE;
524	}
525
526	if (clusters == 0) {
527		DPRINTF(1, ("truncating node to zero bytes\n"));
528		if (node->cluster == 0)
529			return B_OK;
530
531		c = node->cluster;
532		if ((result = clear_fat_chain(vol, c)) != B_OK)
533			return result;
534
535		node->cluster = 0;
536		node->end_cluster = 0;
537
538		// TODO: don't have to do this this way -- can clean up nicely
539		do {
540			result = vcache_set_entry(vol, node->vnid,
541				GENERATE_DIR_INDEX_VNID(node->dir_vnid, node->sindex));
542			// repeat until memory is freed up
543			if (result != B_OK)
544				snooze(5000LL);
545		} while (result != B_OK);
546
547		/* write to disk so that get_next_dirent doesn't barf */
548		write_vnode_entry(vol, node);
549		return result;
550	}
551
552	if (node->cluster == 0) {
553		DPRINTF(1, ("node has no clusters. adding %ld clusters\n", clusters));
554
555		if ((result = allocate_n_fat_entries(vol, clusters, &n)) != B_OK)
556			return result;
557
558		node->cluster = n;
559		node->end_cluster = get_nth_fat_entry(vol, n, clusters - 1);
560
561		// TODO: don't have to do this this way -- can clean up nicely
562		do {
563			result = vcache_set_entry(vol, node->vnid,
564				GENERATE_DIR_CLUSTER_VNID(node->dir_vnid, node->cluster));
565			// repeat until memory is freed up
566			if (result != B_OK)
567				snooze(5000LL);
568		} while (result != B_OK);
569
570		/* write to disk so that get_next_dirent doesn't barf */
571		write_vnode_entry(vol, node);
572		return result;
573	}
574
575	i = (node->st_size + vol->bytes_per_sector * vol->sectors_per_cluster - 1)
576		/ vol->bytes_per_sector / vol->sectors_per_cluster;
577	if (i == clusters)
578		return B_OK;
579
580	if (clusters > i) {
581		// add new fat entries
582		DPRINTF(1, ("adding %ld new fat entries\n", clusters - i));
583		if ((result = allocate_n_fat_entries(vol, clusters - i, &n)) != B_OK)
584			return result;
585
586		ASSERT(IS_DATA_CLUSTER(n));
587
588		result = set_fat_entry(vol, node->end_cluster, n);
589		if (result < B_OK) {
590			clear_fat_chain(vol, n);
591			return result;
592		}
593
594		node->end_cluster = get_nth_fat_entry(vol, n, clusters - i - 1);
595		return result;
596	}
597
598	// traverse fat chain
599	c = node->cluster;
600	n = get_fat_entry(vol, c);
601	for (i = 1; i < clusters; i++) {
602		if (!IS_DATA_CLUSTER(n))
603			break;
604
605		c = n;
606		n = get_fat_entry(vol, c);
607	}
608
609	ASSERT(i == clusters);
610	ASSERT(n != END_FAT_ENTRY);
611
612	if (i == clusters && n == END_FAT_ENTRY)
613		return B_OK;
614
615	if (n < 0)
616		return n;
617
618	if (n != END_FAT_ENTRY && !IS_DATA_CLUSTER(n))
619		return B_BAD_VALUE;
620
621	// clear trailing fat entries
622	DPRINTF(1, ("clearing trailing fat entries\n"));
623	if ((result = set_fat_entry(vol, c, 0x0fffffff)) != B_OK)
624		return result;
625
626	node->end_cluster = c;
627	return clear_fat_chain(vol, n);
628}
629
630
631void
632dump_fat_chain(nspace *vol, uint32 cluster)
633{
634	dprintf("fat chain: %ld", cluster);
635	while (IS_DATA_CLUSTER(cluster)) {
636		cluster = get_fat_entry(vol, cluster);
637		dprintf(" %ld", cluster);
638	}
639
640	dprintf("\n");
641}
642
643/*
644status_t fragment(nspace *vol, uint32 *pattern)
645{
646	uint32 sector, offset, previous_entry, i, val;
647	uchar *buffer;
648	bool dirty = FALSE;
649
650	srand(time(NULL)|1);
651
652	if (vol->fat_bits == 16)
653		previous_entry = 0xffff;
654	else if (vol->fat_bits == 32)
655		previous_entry = 0x0fffffff;
656	else {
657		dprintf("fragment: only for FAT16 and FAT32\n");
658		return ENOSYS;
659	}
660
661	sector = vol->reserved_sectors + vol->active_fat * vol->sectors_per_fat +
662			((vol->total_clusters + 2 - 1) * (vol->fat_bits / 8)) /
663					vol->bytes_per_sector;
664	offset = ((vol->total_clusters + 2 - 1) * (vol->fat_bits / 8)) %
665			vol->bytes_per_sector;
666
667	buffer = (uchar *)get_block(vol->fd, sector, vol->bytes_per_sector);
668	if (!buffer) {
669		dprintf("fragment: error getting fat block %lx\n", sector);
670		return EINVAL;
671	}
672
673	val = pattern ? *pattern : rand();
674
675	for (i=vol->total_clusters+1;i>=2;i--) {
676		if (val & (1 << (i & 31))) {
677			if (vol->fat_bits == 16) {
678				if (read16(buffer, offset) == 0) {
679					buffer[offset+0] = (previous_entry     ) & 0xff;
680					buffer[offset+1] = (previous_entry >> 8) & 0xff;
681					previous_entry = i;
682					dirty = TRUE;
683					vol->free_clusters--;
684				}
685			} else {
686				if (read32(buffer, offset) == 0) {
687					buffer[offset+0] = (previous_entry      ) & 0xff;
688					buffer[offset+1] = (previous_entry >>  8) & 0xff;
689					buffer[offset+2] = (previous_entry >> 16) & 0xff;
690					buffer[offset+3] = (previous_entry >> 24) & 0xff;
691					previous_entry = i;
692					dirty = TRUE;
693					vol->free_clusters--;
694				}
695			}
696		}
697
698		if (!offset) {
699			if (dirty) {
700				mark_blocks_dirty(vol->fd, sector, 1);
701				mirror_fats(vol, sector, buffer);
702			}
703			release_block(vol->fd, sector);
704
705			dirty = FALSE;
706			sector--;
707
708			buffer = (uchar *)get_block(vol->fd, sector,
709					vol->bytes_per_sector);
710			if (!buffer) {
711				dprintf("fragment: error getting fat block %lx\n", sector);
712				return EINVAL;
713			}
714		}
715
716		offset = (offset - vol->fat_bits / 8 + vol->bytes_per_sector) %
717				vol->bytes_per_sector;
718
719		if (!pattern && ((i & 31) == 31))
720			val = rand();
721	}
722
723	if (dirty) {
724		mark_blocks_dirty(vol->fd, sector, 1);
725		mirror_fats(vol, sector, buffer);
726	}
727	release_block(vol->fd, sector);
728
729	vol->last_allocated = (rand() % vol->total_clusters) + 2;
730
731	return B_OK;
732}
733*/
734
735