sbin/fsck_msdosfs/fat.c

64  * For each cluster, we use 1 bit to represent if it's a head cluster
72  * corresponding cluster was a "head" cluster.
74  * We use head bitmap to identify lost chains: a head cluster that was
75  * not being claimed by any file or directories is the head cluster of
81  * by finding out the 1's in the head bitmap.
399 	 * Cache hit: if we already have the chunk, move it to list head
805  * Read or map a FAT and populate head bitmap
860 		perr("No space for head bitmap for FAT clusters (%zu)",
937 	 * Traverse the FAT table and populate head map.  Initially, we
938 	 * consider all clusters as possible head cluster (beginning of
940 	 * by marking every non-head nodes as such (detailed below) and
946 	 *    head node.
950 	 *    head cluster.  Note that during the scan, every cluster is
956 	 * head nodes, because they were never claimed by any other
960 	 * where these head nodes would be marked as non-head.
962 	 * In the final pass, all head nodes should be cleared, and if
963 	 * there is still head nodes, these would be leaders of lost
1036 checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
1042 	 * We expect that the caller to give us a real, unvisited 'head'
1047 	assert(valid_cl(fat, head));
1048 	assert(fat_is_cl_head(fat, head));
1051 	 * Immediately mark the 'head' cluster that we are about to visit.
1053 	fat_clear_cl_head(fat, head);
1060 	 * With a valid head node at hand, we expect all subsequent
1070 	prev_cl = current_cl = head;
1095 		    head, rsrvdcltype(next_cl));
1099 		    head,
1119  * Clear cluster chain from head.
1122 clearchain(struct fat_descriptor *fat, cl_t head)
1127 	current_cl = head;
1249 	cl_t head;
1264 	for (head = CLUST_FIRST;
1265 	    chains > 0 && head < boot->NumClusters;
1271 		if (head % LONG_BIT == 0 &&
1272 		    !fat_is_cl_head_in_range(fat, head)) {
1273 			head += LONG_BIT;
1276 		if (fat_is_cl_head(fat, head)) {
1277 			ret = checkchain(fat, head, &chainlength);
1281 				    head, chainlength);
1282 				mod |= ret = reconnect(fat, head,
1288 				clearchain(fat, head);
1293 		head++;
1316 				for (head = CLUST_FIRST; head < boot->NumClusters; head++)
1317 					if (fat_get_cl_next(fat, head) == CLUST_FREE) {
1318 						boot->FSNext = head;