sbin/fsck_msdosfs/fat.c

62  * For each cluster, we use 1 bit to represent if it's a head cluster
70  * corresponding cluster was a "head" cluster.
72  * We use head bitmap to identify lost chains: a head cluster that was
73  * not being claimed by any file or directories is the head cluster of
79  * by finding out the 1's in the head bitmap.
397 	 * Cache hit: if we already have the chunk, move it to list head
803  * Read or map a FAT and populate head bitmap
858 		perr("No space for head bitmap for FAT clusters (%zu)",
935 	 * Traverse the FAT table and populate head map.  Initially, we
936 	 * consider all clusters as possible head cluster (beginning of
938 	 * by marking every non-head nodes as such (detailed below) and
944 	 *    head node.
948 	 *    head cluster.  Note that during the scan, every cluster is
954 	 * head nodes, because they were never claimed by any other
958 	 * where these head nodes would be marked as non-head.
960 	 * In the final pass, all head nodes should be cleared, and if
961 	 * there is still head nodes, these would be leaders of lost
1034 checkchain(struct fat_descriptor *fat, cl_t head, size_t *chainsize)
1040 	 * We expect that the caller to give us a real, unvisited 'head'
1045 	assert(valid_cl(fat, head));
1046 	assert(fat_is_cl_head(fat, head));
1049 	 * Immediately mark the 'head' cluster that we are about to visit.
1051 	fat_clear_cl_head(fat, head);
1058 	 * With a valid head node at hand, we expect all subsequent
1068 	prev_cl = current_cl = head;
1093 		    head, rsrvdcltype(next_cl));
1097 		    head,
1117  * Clear cluster chain from head.
1120 clearchain(struct fat_descriptor *fat, cl_t head)
1125 	current_cl = head;
1247 	cl_t head;
1262 	for (head = CLUST_FIRST;
1263 	    chains > 0 && head < boot->NumClusters;
1269 		if (head % LONG_BIT == 0 &&
1270 		    !fat_is_cl_head_in_range(fat, head)) {
1271 			head += LONG_BIT;
1274 		if (fat_is_cl_head(fat, head)) {
1275 			ret = checkchain(fat, head, &chainlength);
1279 				    head, chainlength);
1280 				mod |= ret = reconnect(fat, head,
1286 				clearchain(fat, head);
1291 		head++;
1314 				for (head = CLUST_FIRST; head < boot->NumClusters; head++)
1315 					if (fat_get_cl_next(fat, head) == CLUST_FREE) {
1316 						boot->FSNext = head;