Portable electronic device having a log-structured file system in flash memory

• US 6,535,949 B1
• Filed: 04/19/1999
• Issued: 03/18/2003
• Est. Priority Date: 04/19/1999
• Status: Expired due to Term

• Current Assignee: Blackberry Limited
• Original Assignee: Research In Motion Limited (Blackberry Limited)
• Inventors: Parker, Kenneth W.
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Choi, Woo H.
• Application Number:
  US09/294,934
• Time in Patent Office: 1,429 Days
• Field of Search: 707/205, 707/206, 707/101, 711/103, 711/104, 711/105, 711/159, 711/111-115, 711/154, 711/160, 711/173
• US Class Current: 711/103
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 7/16 Storage of analogue signals in digital stores using an arrangement comprising analogue/digital [A/D] converters, digital memories and digital/analogue [D/A] converters
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A portable electronic device includes a log-structured file system implemented in flash memory, The log-structured file system includes a write function for storing contiguous data records to the flash memory in the form of at least one data log, although the system may write data records to the flash memory using a plurality of data logs. The log-structured file system also includes a read function for retrieving data records from the one or more logs using a plurality of memory mapped pointers, which may be stored in an associated RAM index, or which may be implemented as an index stored in the flash memory. A clean-log function is also provided for eliminating inactive records from the log so that new data can be appended to the end of the log. The various functions associated with the log-structured file system are implemented as at least three software modules, a read module, a write module and a clean-log module, although other configurations are possible. The portable electronic device may include a two-way RF transceiver for sending and receiving data from the device, and may also include a plurality of application programs that are configured to interact with the log-structured file system, as well as other software modules for controlling the operation of the portable electronic device.

Claims

1. A portable electronic device, including:

a flash memory store comprising a plurality of erase blocks;

a log-structured file system for storing a plurality of logs of contiguous data records in the flash memory store, for reading data from the flash memory store using a plurality of memory mapped pointers that point to the individual data records, and for cleaning inactive records from the flash memory store in order to make room for additional data, wherein at least one of the logs of contiguous data records stores records that change frequently, and at least one other log stores data records that change infrequently, and wherein the log-structured file system is configured to determine whether a current erase block into which a data record is to be stored includes available space to store the data record, and to clean inactive records from a next erase block adjacent to the current erase block in the flash memory store where the current erase block does not include available space to store the data record;

wherein the log-structured file system further includes a plurality of pointers for managing the storing of data to the flash memory store and the cleaning of inactive records from the flash memory store;

wherein the plurality of pointers includes a log point indicating a position in the current erase block at which the data record is to be stored, and an erase point indicating a beginning of the next erase block; and

wherein the log-structured file system is further configured to determine an amount of available space in the current erase block by comparing the erase point and the log point.

2. The portable electronic device of claim 1, wherein the log-structured file system is configured to determine that the current erase block includes available space to store the data record where the amount of available space is greater than a size of the data record and a minimum space required for cleaning the next erase block.

3. The portable electronic device of claim 2, wherein the log-structured file system includes active records and inactive records, and wherein the plurality of pointers further includes a clean point indicating a position of a next active record after the erase point in the log-structured file system.

4. The portable electronic device of claim 3, wherein the log-structured file system is further configured to mark a particular record in the log-structured file system as inactive, and to move the clean point to a position of a next active record in the log-structured file system, when a new record replacing the particular record is written stored in the log-structured file system.

5. The portable electronic device of claim 4, wherein the log-structured file system is further configured to clean inactive records from the next erase block when the clean point is moved to an end of the next erase block.

6. The portable electronic device of claim 3, wherein the log-structured file system is further configured to copy active records from the next erase block to the current erase block, and to mark copied active records in the next erase block as inactive where the current erase block does not include available space to store the data record.

7. A method of managing a log-structured file system in a flash memory comprising a plurality of erase blocks, the log-structured file system storing a plurality of logs of contiguous records in the flash memory store, the method comprising the steps of:

receiving a data record to be written into a current erase block in the flash memory store;

determining whether the current erase block includes available space to write the data record; and

cleaning inactive records from a next erase block adjacent to the current erase block in the flash memory store where the current erase block does not include available space to write the data record;

wherein the log-structured file system further comprises a plurality of pointers, the plurality of pointers including a log point indicating a position in the current erase block at which the data record is to be written, and an erase point indicating a beginning of the next erase block, and wherein the step of determining whether the current erase block includes available space to write the data record comprises the step of determining an amount of available space between the erase point and the log point.

8. The method of claim 7, wherein the step of receiving a data record comprises the step of receiving a data record from one of a plurality of application programs that read and write data to the flash memory store using the log-structured file system.

9. The method of claim 8, wherein the plurality of application programs include:

an e-mail application and at least one of an organizer application, a calendar application, a to-do list application, an address book application, a billable hours application and a timecard application.

10. The method of claim 7, wherein the step of determining whether the current erase block includes available space to write the data record further comprises the step of determining whether the amount of available space is greater than a size of the data record and a minimum space required for cleaning the next erase block.

11. The method of claim 7, wherein the log-structured file system includes active records and inactive records, and wherein the- step of cleaning inactive records from a next erase block comprises the steps of copying active records from the next erase block to the current erase block, marking copied active records in the next erase block as inactive, and cleaning the inactive records in the next erase block when all active records in the next erase block have been copied to the current erase block and marked as inactive.

12. The method of claim 7, wherein the log-structured file system includes active records and inactive records, further comprising the steps of:

determining whether the next erase block includes active records; and

cleaning inactive records in the next erase block where the next erase block includes no active records.