1. Introduction of Nand Flash

Non-volatile flash memory Flash is widely used in embedded systems because of its fast speed, low cost and high density. Flash memory has two main types: NOR and NAND. NOR type is more suitable for storing program code; The NAND type can be used as a mass data store.
A Nand Flash chip is divided into many blocks, and each block is composed of many chunks. Each chunk is composed of two regions: data and spare. The data region stores file data, spare region stores bad block information, ECC check, and so on. We take K9F2G08X0A as an example, as shown in Fig.

1. K9F2G08X0A is 2,112 Mbit (2,214,592,512 bit) in size and contains 2048 BLOCK s, each of which contains 64 pages and each of which contains 2112 bytes.
2. A page of 212 size consists of a data area (2K) and a SPARE area (64Bytes), where the SPARE area stores bad block information, ECC checks, and so on.
3. Data can be read in bytes when read, but the minimum erase unit is a block.
4. Bad blocks in the device are randomly distributed. Bad blocks are marked on the first or second page of the bad blocks when they leave the factory, and they are marked as values other than 0xFF. FLASH should be scanned and bad block information recorded on first use.
5. All flash devices suffer from bit exchange. Error detection/error correction (EDC/ECC) algorithms should be used to ensure data reliability in use. Once an ECC error is found, the block in which the data resides should be marked as a bad block

For data, the most basic storage and deletion units are chunk and block, so this section describes the source code for chunk and block related operations in yaffs2.

2. Chunk-related operations

2.1 Types of chunk record data

There are three types of data recorded on Nand Flash, check point data, object header, and file data. The data structure for recording chunk status is as follows:

struct yaffs_ext_tags {
	unsigned chunk_used;	/*  Status of the chunk: used or unused */
	unsigned obj_id;	/* If 0 this is not used */
	unsigned chunk_id;	/* If 0 this is a header, else a data chunk */
	unsigned n_bytes;	/* Only valid for data chunks */

	/* The following stuff only has meaning when we read */
	enum yaffs_ecc_result ecc_result;
	unsigned block_bad;

	/* YAFFS 1 stuff */
	unsigned is_deleted;	/* The chunk is marked deleted */
	unsigned serial_number;	/* Yaffs1 2-bit serial number */

	/* YAFFS2 stuff */
	unsigned seq_number;	/* The sequence number of this block */

	/* Extra info if this is an object header (YAFFS2 only) */
	unsigned extra_available;	/* Extra info available if not zero */
	unsigned extra_parent_id;	/* The parent object */
	unsigned extra_is_shrink;	/* Is it a shrink header? */
	unsigned extra_shadows;	/* Does this shadow another object? */

	enum yaffs_obj_type extra_obj_type;	/* What object type? */

	loff_t extra_file_size;		/* Length if it is a file */
	unsigned extra_equiv_id;	/* Equivalent object for a hard link */
};

• Checkpoint data YAFFS2 allocates storage space to record check point data according to a block, that is, a block is used to either record check point data entirely or record normal data entirely. Chuk's tag.seq_number is multiplexed to "record block seq_number" or "denote that a block records check point data". The possibility of this reuse is based on the block. Seq_ The size of a number is within a fixed interval.
• Object header tag. ChukId equals 0, indicating that the corresponding chunk's data area records the object header and can be tagged. ObjectId found the corresponding file.
• File data tag. ChukId is not equal to 0, then the corresponding chunk's data area records the file data, and tag. The chunkId represents the logical chunk id of the chunk within the file. It can also be tagged. ObjectId found the corresponding file.

Usage of 2.2 chunk

In the dev structure, there is a parameter u8 *chunk_bits, records the use of chunks, one for each bit, and YAFFS2 uses this data to record whether chunks are being used. This information only exists in memory at runtime, and when YAFFS2 is unmout, the array is recorded as a check point data, which is read out and restored at the next mount. In the file "yaffs_bitmap.c", the code for the change function of bit corresponding to a chunk is as follows. The content is simple, and it is not explained in detail. You may know what the function does according to the function name.

static inline u8 *yaffs_block_bits(struct yaffs_dev *dev, int blk)
{
	if (blk < (int)dev->internal_start_block ||
	    blk > (int)dev->internal_end_block) {
		yaffs_trace(YAFFS_TRACE_ERROR,
			"BlockBits block %d is not valid",
			blk);
		BUG();
	}
	return dev->chunk_bits +
	    (dev->chunk_bit_stride * (blk - dev->internal_start_block));
}

void yaffs_verify_chunk_bit_id(struct yaffs_dev *dev, int blk, int chunk)
{
	if (blk < (int)dev->internal_start_block ||
	    blk > (int)dev->internal_end_block ||
	    chunk < 0 || chunk >= (int)dev->param.chunks_per_block) {
		yaffs_trace(YAFFS_TRACE_ERROR,
			"Chunk Id (%d:%d) invalid",
			blk, chunk);
		BUG();
	}
}

void yaffs_clear_chunk_bits(struct yaffs_dev *dev, int blk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	memset(blk_bits, 0, dev->chunk_bit_stride);
}

void yaffs_clear_chunk_bit(struct yaffs_dev *dev, int blk, int chunk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	yaffs_verify_chunk_bit_id(dev, blk, chunk);
	blk_bits[chunk / 8] &= ~(1 << (chunk & 7));
}

void yaffs_set_chunk_bit(struct yaffs_dev *dev, int blk, int chunk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	yaffs_verify_chunk_bit_id(dev, blk, chunk);
	blk_bits[chunk / 8] |= (1 << (chunk & 7));
}

int yaffs_check_chunk_bit(struct yaffs_dev *dev, int blk, int chunk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	yaffs_verify_chunk_bit_id(dev, blk, chunk);
	return (blk_bits[chunk / 8] & (1 << (chunk & 7))) ? 1 : 0;
}

int yaffs_still_some_chunks(struct yaffs_dev *dev, int blk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	int i;
	for (i = 0; i < dev->chunk_bit_stride; i++) {
		if (*blk_bits)
			return 1;
		blk_bits++;
	}
	return 0;
}

int yaffs_count_chunk_bits(struct yaffs_dev *dev, int blk)
{
	u8 *blk_bits = yaffs_block_bits(dev, blk);
	int i;
	int n = 0;
	for (i = 0; i < dev->chunk_bit_stride; i++, blk_bits++)
		n += hweight8(*blk_bits);
	return n;
}

2.3 Writing to chunk

Writing data to a chunk is in the yaffs_guts.c file, which is the core code file of yaffs2. The most important functions for writing data are "yaffs_alloc_chunk" and "yaffs_write_new_chunk", which represent assigning a new chunk and writing data to a new chunk. The code is as follows, in which we delete the code for printing information.

static int yaffs_alloc_chunk(struct yaffs_dev *dev, int use_reserver,
			     struct yaffs_block_info **block_ptr)
{
	int ret_val;
	struct yaffs_block_info *bi;

	if (dev->alloc_block < 0) {
		/* Get next block to allocate off */
		dev->alloc_block = yaffs_find_alloc_block(dev);
		dev->alloc_page = 0;
	}

	/*use_reserver Indicates whether reserved space is used, normally 0, and this parameter is set to 1 only if storage space needs to be allocated for garbage collection*/
	if (!use_reserver && !yaffs_check_alloc_available(dev, 1)) {
		return -1;
	}

	if (dev->alloc_block >= 0) {
		bi = yaffs_get_block_info(dev, dev->alloc_block);

		ret_val = (dev->alloc_block * dev->param.chunks_per_block) +
		    dev->alloc_page;        /*ret_val Is the total number of the chunk in the whole device*/
		bi->pages_in_use++;
		yaffs_set_chunk_bit(dev, dev->alloc_block, dev->alloc_page);  /*Change the page of the corresponding bitmap*/

		dev->alloc_page++;
		dev->n_free_chunks--;

		/* If the block is full, set the block status accordingly*/
		if (dev->alloc_page >= dev->param.chunks_per_block) {
			bi->block_state = YAFFS_BLOCK_STATE_FULL;
			dev->alloc_block = -1;
		}

		if (block_ptr)
			*block_ptr = bi;

		return ret_val;
	}

	return -1;
}

static int yaffs_write_new_chunk(struct yaffs_dev *dev,
				 const u8 *data,
				 struct yaffs_ext_tags *tags, 
				 int use_reserver)
{
	u32 attempts = 0;
	int write_ok = 0;
	int chunk;

	yaffs2_checkpt_invalidate(dev);

	do {
		struct yaffs_block_info *bi = 0;
		int erased_ok = 0;

		chunk = yaffs_alloc_chunk(dev, use_reserver, &bi);
		if (chunk < 0) {
			/* no space */
			break;
		}

		/* let's give it a try */
		attempts++;

		if (dev->param.always_check_erased)
			bi->skip_erased_check = 0;

		if (!bi->skip_erased_check) {
			erased_ok = yaffs_check_chunk_erased(dev, chunk);
			if (erased_ok != YAFFS_OK) {
				yaffs_chunk_del(dev, chunk, 1, __LINE__);
				yaffs_skip_rest_of_block(dev);
				continue;
			}
		}

		write_ok = yaffs_wr_chunk_tags_nand(dev, chunk, data, tags);

		if (!bi->skip_erased_check)
			write_ok = yaffs_verify_chunk_written(dev, chunk, data, tags);

		if (write_ok != YAFFS_OK) {
			yaffs_handle_chunk_wr_error(dev, chunk, erased_ok);
			continue;
		}

		bi->skip_erased_check = 1;

		yaffs_handle_chunk_wr_ok(dev, chunk, data, tags);
	} while (write_ok != YAFFS_OK &&
		 (yaffs_wr_attempts == 0 || attempts <= yaffs_wr_attempts));

	if (!write_ok)
		chunk = -1;

	if (attempts > 1) {
		dev->n_retried_writes += (attempts - 1);
	}
	return chunk;
}

The final write is to use the function "yaffs_wr_chunk_tags_nand", which uses the statement dev->tagger when writing data. Write_ Chunk_ Tags_ Fn, uses the method of pointer function, which makes the function more flexible to use. For the initialization of function, it is placed in the file "yaffs_tags compat.c". The function "yaffs_tags_compat_wr" is the function that it eventually uses to write data. The following table:

static int yaffs_tags_compat_wr(struct yaffs_dev *dev, int nand_chunk,
			 const u8 *data, const struct yaffs_ext_tags *ext_tags)
{
	struct yaffs_spare spare;
	struct yaffs_tags tags;

	yaffs_spare_init(&spare);

	if (ext_tags->is_deleted)
		spare.page_status = 0;
	else {
		tags.obj_id = ext_tags->obj_id;
		tags.chunk_id = ext_tags->chunk_id;

		tags.n_bytes_lsb = ext_tags->n_bytes & (1024 - 1);

		if (dev->data_bytes_per_chunk >= 1024)
			tags.n_bytes_msb = (ext_tags->n_bytes >> 10) & 3;
		else
			tags.n_bytes_msb = 3;

		tags.serial_number = ext_tags->serial_number;

		if (!dev->param.use_nand_ecc && data) {
			yaffs_ecc_calc(data, spare.ecc1);
			yaffs_ecc_calc(&data[256], spare.ecc2);
		}
		yaffs_load_tags_to_spare(dev, &spare, &tags);
	}
	return yaffs_wr_nand(dev, nand_chunk, data, &spare);
}

This includes the generation of ecc checkcodes, the calculation of spare data, and the final write calls into the function yaffs_wr_nand, whose final write data is the dev->drv called. Drv_ Write_ Chunk_ Fn, also known as pointer function, ultimately points to the underlying flash driver function. This completes the chunk writing.

2.4 Delete chunk

Because Nand Flash writes in chunks and blockdeletes, deleting a chunk here means invalidating the chunk until it is deleted. "yaffs_chunk_del" and "yaffs_soft_del_chunk" can both delete a chunk, the former updating u8 *chunk_bits and bi->pagesInUse, which only updates soft_del_pages. In addition, the former causes an erase block operation (calling the function yaffs_block_become_dirty), while the latter does not. The code is as follows:

void yaffs_chunk_del(struct yaffs_dev *dev, int chunk_id, int mark_flash,
		     int lyn)
{
	int block;
	int page;
	struct yaffs_ext_tags tags;
	struct yaffs_block_info *bi;

	if (chunk_id <= 0)
		return;

	dev->n_deletions++;
	block = chunk_id / dev->param.chunks_per_block;
	page = chunk_id % dev->param.chunks_per_block;

	bi = yaffs_get_block_info(dev, block);

	yaffs2_update_oldest_dirty_seq(dev, block, bi);

	if (!dev->param.is_yaffs2 && mark_flash &&
	    bi->block_state != YAFFS_BLOCK_STATE_COLLECTING) {

		memset(&tags, 0, sizeof(tags));
		tags.is_deleted = 1;
		yaffs_wr_chunk_tags_nand(dev, chunk_id, NULL, &tags);
		yaffs_handle_chunk_update(dev, chunk_id, &tags);
	} else {
		dev->n_unmarked_deletions++;
	}

	if (bi->block_state == YAFFS_BLOCK_STATE_ALLOCATING ||
	    bi->block_state == YAFFS_BLOCK_STATE_FULL ||
	    bi->block_state == YAFFS_BLOCK_STATE_NEEDS_SCAN ||
	    bi->block_state == YAFFS_BLOCK_STATE_COLLECTING) {
		dev->n_free_chunks++;
		yaffs_clear_chunk_bit(dev, block, page);
		bi->pages_in_use--;

		if (bi->pages_in_use == 0 &&
		    !bi->has_shrink_hdr &&
		    bi->block_state != YAFFS_BLOCK_STATE_ALLOCATING &&
		    bi->block_state != YAFFS_BLOCK_STATE_NEEDS_SCAN) {
			yaffs_block_became_dirty(dev, block);
		}
	}
}

static void yaffs_soft_del_chunk(struct yaffs_dev *dev, int chunk)
{
	struct yaffs_block_info *the_block;
	unsigned block_no;

	block_no = chunk / dev->param.chunks_per_block;
	the_block = yaffs_get_block_info(dev, block_no);
	if (the_block) {
		the_block->soft_del_pages++;
		dev->n_free_chunks++;
		yaffs2_update_oldest_dirty_seq(dev, block_no, the_block);
	}
}

3. Block-related operations

3.1 block Content

Structural yaffs_BlockInfo records the runtime information of blocks. When the yaffs2 file system is running, BlockInfo for each block is recorded in an array, dev->block_ Info can point to this array, which exists in memory at run time and is recorded as checkpoint data when Yaffs2 is uninstalled, read out and restored the next time the file system is mounted. Yaffs_ The BlockInfo structure is as follows:

struct yaffs_block_info {
	s32 soft_del_pages:10;	/* Number of softly deleted pages*/
	s32 pages_in_use:10;	/* Number of page s allocated for use*/
	u32 block_state:4;	    /* The state of the block */
	u32 needs_retiring:1;	/* Failure of data on block, need to recycle*/
	u32 skip_erased_check:1;/* Skip Recycle Check*/
	u32 gc_prioritise:1;	/* ecc Check invalid, block needs priority GC*/
	u32 chunk_error_strikes:3;	/* Number of times ECC checks are allowed to fail*/
	u32 has_summary:1;	    /*Block has summary */
	u32 has_shrink_hdr:1;   /* A block has at least one shrink header */
	u32 seq_number;		    /*The order in which blocks are assigned, and when garbage is collected, determine if the block is suitable for recycling*/
};

The meaning of each parameter has been explained in the comment, not in too much detail, seq_number indicates the order in which blocks are used. Smaller numbers indicate earlier blocks are used, and vice versa. block's seq_number plays a very important role in gc and scan on power.
Also note that when the file system is running, dev->alloc_in the global information structure Block records the block index that is allocating the chunk, dev->alloc_ Page records the number of chunks that have been allocated on the blocks being allocated. The status of the blocks being allocated is "allocating", and when the chunks on the blocks are all allocated, that is, they are all outdated by the program, the status of the blocks is "full".

3.2 block Deletion

The important operations for blocks are "yaffs_block_become_dirty" in the "yaffs_guts.c" file and "yaffs_erase_block" and "yaffs_mark_bad" in the "yaffs_nand.c" file. The main purpose of blocks collection is to use them in the file system. This is not discussed in detail here. When we analyze this part of garbage collection later, Then focus on code analysis.