Many consumer products need to record and play digital video and audio data. If you need to do something similar in your next device, here are some design guidelines for implementing the filesystem.
Designing and implementing an operational digital multimedia filesystem can be challenging. Such a filesystem must typically be implemented within a low-cost consumer product like a digital video recorder or MP3 player. To be useful for multimedia record and playback, the device's platform must have an operating system, device drivers, multimedia codecs, a user interface for selecting the data to be played, and many other complex or expensive-to-develop components. The filesystem must typically be able to:
- Pause and resume delayed live programs (requires simultaneous recording and playback)
- Record two different programs simultaneously (if two tuners are available)
- Fast forward and rewind through the playing program (with visual or audio cues taken from the actual content)
- Skip around in the digital multimedia data stream (forward to skip commercials, backward for instant replays)
- Save numerous recorded programs to disk and organize them so they can be individually selected for playback
Since a number of products now on the market allow recording and playback of digital multimedia, you'd think that some quick research would provide an introduction to embedding multimedia filesystem in a product. You'll find, however, that none of the video or audio products on the market have released much information about their filesystem format.
You'll also discover that the DVD file format is quite secret. Gaining legitimate access to it requires a good sum of money and the signature of a corporate officer. Some of the format is documented on hacker web sites, but it's not obvious what parts of that documentation can be trusted. Streaming file formats commonly used by web sites and PC browsers are also amazingly difficult to find information about, are complex, and generally use data rates well below that of the television programs I want my device to record.
There are big issues with flow control. Off-air video arrives in a more or less continuous stream. When digitized and compressed, the video data rate is significantly slower than the transfer rate of a hard disk. This means that previously recorded data may be played from the hard disks at rates much greater than the normal speed. The steady state play rate of the multimedia must be artificially restrained or flow controlled.
Unlike the continuous stream of off-air video, data from the hard disk is broken up into chunks that must be periodically fetched. As a result there are big flow-control, buffering, and latency issues. Buffer too little and your video processing may underflow if a disk seek takes too long or the processor gets distracted at a critical time. Buffer too much and channel change times increase, more RAM is consumed, and the product cost goes up. Also, careful system analysis and design is needed to avoid overflows and underflows during transitions from play to pause to rewind, and so on.
Like any file, multimedia data are stored in “chunks” on the disk. These chunks, however, are typically a large multiple of the native sector size of the disk drive. For example, a common disk-sector size is 512 bytes, whereas we have found a 512KB chunk (1024 consecutive sectors) far better for storing high data rate (2 to 4Mbps) MPEG-2 video streams. Since seek times tend to dominate overall disk access times, reading or writing a large series of consecutive disk sectors is much more bandwidth efficient than skipping all around the disk.
Even so, playing a recorded multimedia file requires a way to quickly find chunk N+1 while chunk N is being output. A disk seek may still be required between chunks, but we'll also need a way for the software to determine where the start of the next chunk will be. One approach to storing and retrieving a multimedia program is to start writing it at some disk chunk and continue to use sequential chunks until the program finishes. Although this will work, it is certainly suboptimal and introduces major fragmentation problems as programs are deleted.
A more robust design allows the chunks that make up a given file to be scattered around the disk. Such a design must include a way to find all the chunks in the desired order. A file allocation table (FAT) approach works well.
Since the device may be accidentally or purposefully powered down, the FAT describing each program needs to be stored in some nonvolatile way. However, if the FAT is stored on the disk drive, access to every chunk of multimedia data will require two disk accesses (one to access the FAT data to determine where the next chunk lives, the other to actually read the desired chunk of data). Although data transfer to and from the disk is much faster than digitized and compressed video data, moving the disk drive head around is time consuming. Accessing the disk drive twice for every chunk recorded and every chunk played erases much of the data throughput margin even with the improvement gained by grouping disk sectors into larger chunks.
Streaming multimedia has extreme data throughput requirements, and human eyes and ears are very sensitive to delays and jitter. Disk drives are really fast, but the requirement to record and simultaneously play multimedia suggests that multiple disk accesses per multimedia chunk is a bad idea.
So what's the answer? One approach that I found works is shown in Figures 1 and 2. The general concept is to store the FAT of a recording file in RAM and periodically flush the FAT data to the disk.
Figure 1: Logical disk layout for multimedia storage
Figure 2: FAT records indicate chunk locations
Figure 1 shows how the multimedia filesystem coexists with a standard filesystem on a hard disk. The “directory” provides a reference to the other components of the multimedia filesystem, and is located at a fixed known location. Each recording or already recorded program has a recording or already recorded FAT. Open files (programs actively being recorded or played) have a copy of their FAT present in RAM. Figure 2 shows how the FAT points sequentially to the individual chunks that comprise a multimedia file.
Free space management
There are some subtleties involved in data management. When the system powers up, no FAT is in RAM and nothing is known about the content of the disk. Before anything useful can be done, the system must learn about the content and structure of the disk.
It may sound obvious, but at least some disk free space must be found before a program can be recorded and the beginning of a program must be found before it can be played. One solution is the “directory” residing at a known location on the disk. The directory tells you interesting things about each program like its name, the date it was recorded, and where to find the associated FAT.
But how about the very first time the system powers up? The disk has no directory and no structure. Obviously some type of a format function is needed, as well as a way to determine if a disk has already been formatted. Envision an implementation where a newly formatted disk has one filethe “free space file.” Recording on such a disk involves stealing chunks from the free space file, filling them with multimedia data, entering a pointer to each chunk in the FAT associated with the recording, and periodically flushing the FAT to disk. When the program is done, we need to close the file, write the final FAT to disk, update directory information, and make sure any unused RAM space is available for recording new files.
Opening a file for recording is significantly different from opening an already recorded file for playing. In the case of playing a file, all or part of the archived FAT must be loaded into RAM before play starts. Cost-sensitive implementations with limited RAM may find it advantageous to load only part of the FAT into RAM at any given time. If only part of the FAT is loaded, however, the implementation must be careful to anticipate needing more FAT entries as the program plays. This becomes interesting in fast forward and rewind scenarios where later or earlier portions of the FAT data must be dynamically fetched.
For the product to work properly, the fetching must be handled under worst-case timing. To play a file, the multimedia data chunk associated with each sequential FAT entry is read from the disk and handed to the audio/video subsystem, with appropriate attention to buffering and flow control. Hopping around in the multimedia data stream (as in a commercial skip feature) necessitates an entire series of synchronizations to ensure that fetching data, buffering, processing, and so on, are sequenced correctly to prevent freezes, jerks, and jitter.
Deleting a recorded program involves returning all its multimedia chunks to the free space pool, updating the directory, and a few other details. Deleting a file introduces a series of issues that must be resolved prior to shipping a product. The free space is now fragmented, so the space allocation algorithm must be able to handle that. Subtler issues include handling gaps in the directory and dynamically returning the chunks to free space while the system is running.
Similar issues arise when power is turned off during recording and the file is not properly closed. The next time it is powered on, the confused system necessitates a recovery operation (best done before any other access is made to the disk). The system must have a relatively foolproof method of determining if a file exists, if it is open or perhaps not properly closed, and a variety of other operational conditions.
Let's take a look at the functions we need for implementing multimedia on an embedded platform. Standard disk functions such as open, close, read, write, seek, delete, and format are indispensable, but the multimedia nature of the application may require a somewhat different implementation (especially considering the needs of reading forward and backward to support fast forward and rewind).
Other, more application-specific disk functions include getting and setting program information, time tracking and computation to support hopping around in the file, debug utilities, and utilities to support the user interface. Finally, disk defragmentation and corruption recovery software must be completed before the product can be shipped.
Here's a list of multimedia filesystem (MMFs) functions most systems will require:
MMFsInit() Called at power up to initialize the subsystem.
MMFsFormat() Certain information on the hard disk must be initialized and the free space must be organized before the disk can be used in the multimedia application. It is also necessary that the application be able to identify that a disk has already been formatted. It is generally a good idea that a version number be associated with each format so that subsequent versions of filesystem software may be backward compatible and allow users to continue viewing their previously recorded material.
MMFsOpen() Used to open an existing file for playback or to create a new file for recording. Depending on the specifics of your application, you may also want to be able to open an existing file and append to it. When a file is opened, one of the blocks of RAM designated for a FAT is consumed. It is filled with a sequential list of blocks to be played for a prerecorded file or with a list of “free” blocks available to use for a recording file. Maintaining an accurate list of open files is critical to the proper operation of the product.
MMFsClose() When a file is closed we make sure that all the multimedia blocks have been written and that the most recent copy of the FAT has been archived to disk. Some housekeeping is also necessary. The file status must be updated to indicate that it is no longer open and the RAM holding its FAT marked available.
MMFsRecover() Sometimes a file will not be properly closed (such as when the user turns off the product while it is recording). This leaves an erroneous “open” status for the file and other potential problems. It may also leave disconnected multimedia chunks scattered around the disk. The erroneous status should be corrected immediately upon power up. Eventually, the lost space may become significant. A background tool that periodically cleans up disconnected chunks would benefit the longevity and usefulness of a product.
MMFsRead() and MMFsWrite() Reading from the disk is a simple matter of accessing the RAM copy of the FAT, getting the disk address of the next chunk data, and reading it. Writing is also simple in concept. Get the disk address where the next chunk of data is to be writtenand write it. Handling of fast forward and rewind may involve some extra details such as skipping over a disk chunk and reading the next one.
MMFsDelete() Deleting a multimedia file is fairly simple in concept. One need only return all the disk chunks associated with the file to the free space pool. Unfortunately, the details of actually implementing this are a little challenging. The first thing to observe is that we need a file's FAT (or at least a portion of it) loaded into RAM before we can identify those disk chunks to be returned to the free space pool. We also need to pay attention to the multitasking aspects of the embedded system. Consumers of disk free space must be prevented from accessing the data structures at the same time as those operations that release disk space to the free space pool. This creates some interesting challenges for the software developer if one allows deletion of a file while another recording is consuming free space. Also observe that the deletion of a file will create a gap in the directory. The gap may be compressed out at the time it is created, perhaps by dynamically changing the directory slot of an active recording. The gap may also be allowed to remain, in which case several functions must be designed to handle gaps in arrays as part of normal operation.
MMFsSeek() Several flavors of seek are useful in a multimedia filesystem. Seeks may be based on time (for example, 10 seconds) or distance (for example, three disk chunks). There are also absolute (restart from the beginning of the file) and relative seeks (skip ahead 30 seconds).
MMFsListDir() Provides a list of all recorded multimedia. Depending on the specific implementation, this function may also present a list of all available free space on the disk.
MMFsModeChange() There are many operational modes in a multimedia filesystem and transitions between them must be synchronized and coordinated. For example, providing a satisfying user experience in a transition from play to fast forward may require dumping “play” data already queued to be displayed and replacing it with specially read and processed “fast forward” data. There is some challenging synchronization work to be done here if your system segregates the read, process, and display operations in different tasks.
MMFsSetInfo() and MMFsGetInfo() These are maintenance functions for setting and retrieving information associated with a stored multimedia file. Examples of this information include the program title, time and date of the recording, a brief program summary, and viewer bookmarks. Advanced implementations might add file attributes such as “hidden” and may even allow password protection of files.
MMFsManageFreeSpace() Free space is the life-blood of a multimedia filesystem. Free space is allocated to a recording and returned upon the deletion of a file. This process must operate efficiently and flawlessly in an environment rich with preemptive scheduling, interrupt processing, and intertask communication and synchronization. Over time the free space on a disk will become fragmented and some may even be lost. Care should be taken to ensure that the management and associated defragmentation of free space are well designed and efficiently implemented.
RawWrite() and RawRead() Low-level routines to manipulate a large contiguous chunk of data starting from a particular disk sector. Contiguous data is good since it lets the hard disk's own firmware worry about head movement, which is its primary skillset. However, too big a disk chunk leads to other problems resulting from the latency associated with processing large numbers of sectors.
A fairly popular notion for multimedia applications is that error recovery should be turned off in the disk driver to prevent the drive from monopolizing the system processor. It's my experience that disruption of system operation by hard disk errors is quite rare. Other system disturbances such as user channel changes, loss of signal, and even system crashes are more likely to interfere with operation.
Finally, you may be surprised how poorly the actual disk driver works. For maximum performance, you'll want the actual disk transfers to be handled by direct memory access, and you'll want a transfer complete interrupt. Don't be surprised if the stress of a multimedia application exposes errors and quirks in disk drivers supplied with your chosen operating system. Multimedia disk usage is way beyond the standard testing parameters for most disk drivers.
But wait there's more
If this sounds like a lot of work, you're getting the right impression. Multimedia filesystem design and implementation is not a trivial task. It must be appropriately staffed and scheduled for success. The fun doesn't stop with the tradeoffs discussed so far. You'll also be amused by such challenges as:
- Picking the correct size for a chunk of multimedia data. Choose too big, and a low bit-rate program will take a long time to fill one chunk. Choose too small, and excessive disk accesses (and, therefore, motion of the disk head) will be required. At each extreme, the performance of the system degrades. I've found that contiguous disk chunks of 512K offer a decent compromise between these conflicting requirements for data rates in the 2 to 4Mbps range.
- Details associated with allocation and management of free space. I favor preallocating big blocks of free space to recording files. This tends to minimize fragmentation (and, thereby, head motion) and has a few other benefits. It also has a few disadvantages.
- Handling FAT overflows when a really long program is recorded. You could also choose an implementation where a FAT is big enough to handle recording a program whose duration is longer than can physically fit on the disk. In this case, the FAT can never overflow. Oh, the engineering tradeoffs! You'll really want to think about this.
- When and how often should the FAT and directory be flushed to disk? Most likely this should be done by a low-priority background task. However, be careful not to introduce a priority inversion.
- Some serious thinking needs to be focused on synchronizing transitions between play, rewind, fast forward, pause, and all the other “trick modes.” Buffers need to be flushed and refilled. The read pointer may need to be repositioned. Even the way reads are done may change vastly between different display modes.
- Task priorities for record and play as related to other system functions. Make sure to include mode synchronization in your analysis. Shifting between play and rewind, fast forward, and the like while the recording is being made is a little tricky. Watch out for system deadlocks, priority inversion, and other problems.
- Many content providers and broadcasters require that data stored on the filesystem be encrypted, so that it cannot be copied. Ultimately, several layers of encryption may be applied.
- Handling big hard drives. “Big” is a relative term. What was big last year is not-so-big this year. Soon, in fact, terabyte drives may be available on the consumer market. Such a drive may well store thousands of recorded multimedia programs. How in the world is all that information to be organized and accessed through a simple user interface?
Of all the projects I have worked on, designing and implementing a multimedia filesystem for a digital set-top box has been one of the most enjoyable and intellectually challenging. A multimedia filesystem needs to handle such a large volume of high-speed data in a consumer-priced platform that the engineering tradeoffs are almost endless. Fortunately, the end result is very satisfying. There is nothing like seeing your product in the hands of consumers and in your own home.
Mike Ficco has BS and MS degrees in electrical engineering from the University of Maryland. He has designed and implemented one of the first dialup gaming networks and one of the first wireless LANs. He is now working on advanced set-top boxes for digital television. Contact him at .