LittleFS-GC

A garbage collector for LittleFS

NOTE: Instead of supplying a set of patch files, I decided to pull in all the original code and keep rebasing this project on top of the upstream repository.

Background

LittleFS is a popular embedded filesystem. One of the design decisions was to only delete blocks as they are needed. Additionally, sometimes blocks need to be relocated which requires deletion and copying of data. Both of these result in many users getting frustrated with the big performance degradation they see once the filesystem gets "dirty" enough to require relocation. I am one of these users, but I really like LittleFS, so this is my attempt to remedy the situation.

My Workaround

There is nothing I can do about the need for relocation, so my approach is to simply make writing and especially relocation as fast as humanly possible. The solution is quite simple actually:
LittleFS assumes that a block needs to be erase before it writes to it for the first time. Erasing flash is slooooow, so LittleFS-GC modifies this behaviour. Blocks only get erased if they are known to be dirty. Otherwise the new code goes straight to writing. As long as the file system is kept clean, writing to it is fast and fairly predictable. Even relocation ( when it happens ) is barely noticeable.

How it works

• The garbage collector keeps a map of the blocks in the file system. It distinguishes blocks that are:
  • used
  • clean ( unused and confirmed to ne in the erased state of all 1-s )
  • dirty ( unused, but not erased yet ).
• Upon mounting:
  • LittleFS-GC traverses the filesystem and records all used blocks.
  • It then updates its internal map to mark all other blocks as dirty.
  • Next, the GC reads all free blocks. If a block is confirmed to be truly clean, it is marked as such in the internal map.
  • Lastly, and optionally, the GC locates the first block that LittleFS will write to and proactively cleans up a configurable number of blocks. This optional step ensures that whenever LittleFS attempts to write for the first time, it will hit a sequence of free and confirmed clean blocks.
• In the background, the GC does the following:
  • Traverses the filesystem to update its used block map. ( This step can surely be replaced with something smarter but I'm not yet proficient with the inner workings of LittleFS )
  • Systematically, cleans all dirty blocks.
• LittleFS is then modified to only call the user-supplied erase function if the GC has that block marked as dirty.

LittleFS-GC uses bitmaps to keep track of used and free blocks. As the name suggests, every block in those bitmaps is represented by a single bit. Therefore, bitmaps must be ( ( LFS_BLOCK_COUNT + 7 ) / 8 ) bytes long. There are two such bitmaps. One tracks the used block and the other tracks the clean blocks.

Usage

First, add the following to your lfs_config.h file:

#define LFS_PROACTIVE_GC                    (1)
#define LFS_GC_INITIAL_FREE_BLOCK_TARGET    (13)

#ifndef LFS_GC_TRACE
    #ifdef LFS_GC_YES_TRACE
        #define LFS_GC_TRACE_(fmt, ...) \
            PutYourPrintfFunctionHere( "LittleFS-GC: " fmt "%s\n", __VA_ARGS__)
        #define LFS_GC_TRACE(...) LFS_GC_TRACE_(__VA_ARGS__, "")
    #else
        #define LFS_GC_TRACE_(...)
    #endif
#endif

• LFS_PROACTIVE_GC simply enables LittleFS-GC
• LFS_GC_INITIAL_FREE_BLOCK_TARGET specifies how many blocks will be cleaned up proactively before lfs_mount() completes. This is an optional feature. Cleaning a few blocks during power-up can improve the consistency of how long it takes to write to a file. This proactive cleanup is not required as the background garbage collection will eventually clean those same blocks anyway.

You also need to create a background task that calls the garbage collector periodically. This is usually a low-priority task. Here's some sample code based on FreeRTOS:

static void FileSystemManagementTask( void * pvParameters)
{
	TickType_t xLastTraversalTime;
	lfs_t * pLfs = (lfs_t *) pvParameters;
	if ( !pLfs )
	{
		DebugPrintf("ERROR missing pLfs");
		goto end_task;
	}

	// Initial long delay to prevent running the GC soon after boot.
	// Lot's of things are happening right at boot....
	vTaskDelay(pdMS_TO_TICKS(10000));

	xLastTraversalTime = xTaskGetTickCount();

	while( true)
	{
		vTaskDelay(pdMS_TO_TICKS(FS_GC_INTERVAL_MS));
		// Skip everything if we are in the middle of an async operation like
		// firmware upgrade or UApp upload. We'll cleanup later. Also skip everything
		// if we have checked all blocks.
		if( AsyncFileOps_IsOperationPending() || !bFileSysMounted || lfs_gc_is_fs_clean( pLfs ) )
		{
			xLastTraversalTime = LastFileSysModifiedTime = xTaskGetTickCount();
			continue;
		}

		// Is it time to traverse the file system looking for work?
		if ( ( xTaskGetTickCount() - xLastTraversalTime) >= pdMS_TO_TICKS(FS_GC_TRAVERSAL_INTERVAL_MS) )
		{
			xLastTraversalTime = xTaskGetTickCount();

			uint32_t StartTime = xTaskGetTickCount();
			lfs_gc_update_usage_map( pLfs );
			uint32_t EndTime = xTaskGetTickCount();
			//DebugPrintf("GC Traversal done in %ums", (EndTime - StartTime));

			continue;
		}
		
		if ( ( xTaskGetTickCount() - LastFileSysModifiedTime ) >= pdMS_TO_TICKS(FS_GC_INTERVAL_MS))
		{
			LastFileSysModifiedTime = xTaskGetTickCount();

			//Check if any blocks can be freed to speed up future file system operations
			uint32_t StartTime = xTaskGetTickCount();
			uint32_t EndTime;

			lfs_gc_do_work(pLfs);
			if( lfs_gc_is_fs_clean( pLfs ) )
			{
				DebugPrintf("FS IS CLEAN, going to sleep...");
			}

			EndTime = xTaskGetTickCount();
			//DebugPrintf("gc done in %ums", (EndTime - StartTime));

			continue;
		}
	}
	
	end_task:
	DebugPrintf("FS Management Task exiting...");
	vTaskDelete( NULL );
}

State of this project.

I'm releasing this code in an effort to contribute to the LittleFS community. I will do my best to periodically rebase this code on the latest LittleFS release, but I do not have time to actively develop this project. I am actually using this in production and I'm not aware of any issues. Let me know if you see a potential problem with my approach, if you find a bug, or if you know of a substantial improvement that can be made to this code.

Help Needed

Currently, LittleFS-GC has to periodically traverse the filesystem in order to update its used block bitmap. This step should only be required at mount time. After mounting, LittleFS should be able to "tell" the garbage collector which blocks should be added or removed from the used block bitmap. I haven't figured this out yet and I don't have much time to work on it. If you are proficient in the inner working of LittleFS I'd love some input or guidance on this task.