On Thursday 11 February 2010 11:29:59 Steve Zook wrote:
> I'm a little murky on an algorithmic aspect of the yaffs2 and I was hoping
> to get educated. I've read all the theory materials but could not find an
> answer to the question.
>
> When an object gets deleted, a new header gets written to media to mark the
> object as deleted. The deleting header should always be, sequence number
> wise, last for that object. When the block containing the deleting header
> gets garbage collected, how does it get decided whether to copy the
> deleting header or to drop it?

This is different for the yaffs1 vs yaffs2 modes of operation. From what 
you're saying it looks like you're talking about the yaffs2 mode of 
operation.

yaffs also tracks the number of data chunks per file. When that number drops 
to zero the header chunk becomes deleted and the gc will no longer copy it.

					object->nDataChunks--;

					if (object->nDataChunks <= 0) {
						/* remeber to clean up the object */
						dev->gcCleanupList[cleanups] =
						    tags.objectId;
						cleanups++;
					}

and
		/* Do any required cleanups */
		for (i = 0; i < cleanups; i++) {
			/* Time to delete the file too */
			object =
			    yaffs_FindObjectByNumber(dev,
						     dev->gcCleanupList[i]);
			if (object) {
				yaffs_FreeTnode(dev,
						object->variant.fileVariant.
						top);
				object->variant.fileVariant.top = NULL;
				T(YAFFS_TRACE_GC,
				  (TSTR
				   ("yaffs: About to finally delete object %d"
				    TENDSTR), object->objectId));
				yaffs_DoGenericObjectDeletion(object);
				object->myDev->nDeletedFiles--;
			}

		}

After that, the object header will be deleted and the object header will no 
longer be copied.

The list clean up is left until the end of the block handling otherwise this 
could cause the object header to be deleted before the block is erased. That 
could cause data chunks to come back from the dead.

As an illustration, consider a block A with some data chunks for a file. The 
only active block in block B is the object header for the file. If we see the 
file's nDataChunks go to zero and immediately delete object header B this 
would immediately cause the erasure of block B before block A is erased. If 
power is lost before block A is deleted then we'd end up with some data 
chunks with no object header.


>
> It seems to me that blocks are being garbage collected in arbitrary order
> (as compared to sequence number order). Thus, when the block that contains
> a deleting header is being garbage collected, there may still be object
> headers (obsolete though they may be) in blocks that have yet to be erased.
> If this is true, the delete header must be copied, otherwise during a later
> mount the object will be resurrected. I don't, however, see any efficient
> way to determine whether any such obsolete object headers exist. There
> might be any number of them and they may get erased in arbitrary order.
> Eventually the deleting header should be discarded but when?

As per above.

One thing I am considering doing is recycling deleted objects from the deleted 
directory rather than always generate new ones. This would cut down on the 
number of objects in use.

-- Charles