Method and apparatus for storing non-volatile configuration information

[0002] 1. Field of the Invention

[0003] The present invention relates generally to computer systems and more specifically to a method and apparatus for storing non-volatile configuration information in a flash memory and accessing this information in a manner which does not negatively impact system performance.

[0004] 2. Description of Related Art

[0005] Traditionally, hardware configuration in computer systems was handled using special protocols which were implemented in the hardware itself. Hardware components were manually configured, and it was likely that a particular system would need to be reconfigured only infrequently. Components for modem computer systems, however, are increasingly designed in a modular fashion which allows the hardware configurations of individual computer systems to be very flexible. Demand for custom configurations has grown along with the flexibility of computer hardware.

[0006] As a result of the flexibility of computer hardware, the configuration of computer systems is becoming an increasingly complex task. This has in turn resulted in a need for special configuration parameters that can be manipulated to control the setup and functionality of both the computer hardware and the software that utilizes the hardware. These configuration parameters are used both by the operating system in automatically configuring the system and by the user in manually configuring the system.

[0007] While the configuration parameters allow system configurations to be easily changed, it is desirable to maintain the current values of the parameters, even when the system is powered down. By maintaining the values of the configuration parameters, the need to entirely reconfigure the system every time it is powered down or rebooted is eliminated. Because the configuration parameters need to be maintained through power cycles, they are referred collectively as non-volatile configuration information, or simply NVCI.

[0008] Many of the configuration parameters are critical to the basic boot process of a computer system. The NVCI must therefore be stored in a manner which is persistent and reliable. It is also desirable to make the NVCI available with the greatest possible performance. Typically, NVCI has been stored in a battery-powered SRAM. Battery-powered SRAM, however, is relatively expensive and data stored in the SRAM may be lost as a result of battery failure. It would therefore be desirable to use a more reliable system for storing NVCI.

[0009] Another problem with traditional implementations of NVCI storage systems is that they typically use either a fixed data format or a table of contents that contains pointers to data objects that comprise the NVCI. Neither of these solutions is able to handle dynamic data types very well. Because the fixed format storage cannot be modified, it simply cannot support dynamic data types. The sizes of data objects are also limited by the original space allocations for the data objects. Although systems that use a table of contents and pointers are more flexible than the fixed-data systems, if dynamic data types are to be supported, they require the use of complicated algorithms to determine space allocations for the data objects.

[0010] One or more of the problems outlined above may be solved by the various embodiments of the present invention. Broadly speaking, the invention comprises storing the NVCI in a flash memory and retrieving a copy of the NVCI into a working memory so that it can be quickly accessed.

[0011] In one embodiment, a computer system includes a processor, a working memory (RAM) and a flash memory. NVCI is stored in the flash memory. When the computer system is booted up, the NVCI is read from the flash memory into the working memory. When the computer system needs to read particular values from the NVCI, the copy of the NVCI in the working memory is read. When the computer system needs to write new values to the NVCI, the system writes to both the copy of the NVCI in the working memory and the copy of the NVCI in the flash memory.

[0012] In one embodiment, the system is configured to store the NVCI in the flash memory in a format which both maximizes the lifetime of the flash memory and enables the system to handle dynamic data types efficiently. The NVCI comprises a plurality of key-value pairs. The key-value pairs are stored serially in the flash memory. In other words, a key is followed by its corresponding value, which is followed by another key, and so on. The key-value pairs may also contain data indicating the size of the key and corresponding value, as well as a checksum which is used to detect errors in the key-value pairs. When the value corresponding to a key is updated, the key and the new value are written to the next available space in the flash memory. The next time the flash memory is read into the working memory, the key-value pairs are read serially from the flash memory. When a second or subsequent occurrence of a key is read, the value previously read into the working memory for that key is overwritten with the subsequent value. The working memory therefore contains only one copy of each key and its corresponding value, even though there may be several different values corresponding to the key in the flash memory.

[0013] In one embodiment, the flash memory comprises a segmented flash memory. Each of the segments of the flash memory can be erased independently of the other segments. The NVCI is stored in one of the segments. When additional key-value pairs are written to the segment and it reaches a predetermined capacity, a new segment is selected and the current NVCI (i.e., each key and its most recent value) are written to the new segment. If each of the segments has previously been used (without being erased), a least-recently used segment is selected and is erased before the current NVCI is written to it.

[0014] One embodiment comprises a method implemented in a computer system for storing NVCI which uses less expensive memory, yet provides higher performance than conventional methods. In this embodiment, NVCI is stored in one or more active segments of a segmented flash memory. The NVCI consists of a series of key-value pairs which are stored in contiguous locations in the flash memory, beginning with the lowest address. When the computer system is started, the key-value pairs are read from the flash memory, beginning with the least recently stored and ending with the most recently stored (in most instances, the key-value pairs are read beginning with the lowest memory address and ending with the highest.) The key-value pairs are inserted into a hash table in working memory. Later-read key-value pairs replace earlier-read key-value pairs which have the same key in the hash table. Read accesses to the NVCI are made to the hash table. Write accesses to the NVCI are made to both the hash table and the flash memory. Write accesses to the hash table replace the values which are already stored in the table. Write accesses to the flash memory are stored in “logging” fashion (i.e., they are stored in the next available memory location.) When an active segment of the flash memory is filled to a threshold capacity, the key-value pairs stored in the hash table are written to a new segment, which then becomes the active segment.

[0015] The present invention includes many other embodiments which will be apparent from this disclosure.

[0016] Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:

[0017] FIG. 1 is a block diagram illustrating the configuration of an exemplary computer system in one embodiment.

[0018] FIG. 2 is a flow diagram illustrating the method by which the NVCI is accessed in one embodiment.

[0019] FIG. 3 is a diagram illustrating the manner in which key-value pairs are stored in a flash memory in one embodiment.

[0020] FIG. 4 is a diagram illustrating the manner in which key-value pairs are stored in a hash table in working memory and replaced by new values.

[0021] FIG. 5 is a diagram illustrating the manner in which key-value pairs are stored in a flash memory and new entries are logged at the end of the previously stored entries.

[0022] While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawing and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

[0023] A preferred embodiment of the invention is described below. It should be noted that this and any other embodiments described below are exemplary and are intended to be illustrative of the invention rather than limiting.

[0024] Referring to FIG. 1, a block diagram illustrating the configuration of an exemplary computer system 10 is shown. Computer system 10 includes a processor 12, a working memory 14 and a flash memory 16. These components are each coupled to a local bus 18. Local bus 18 is coupled to a PCI bus 22 via bus bridge 20. A variety of peripheral devices (e.g., disk drive 24, CD-ROM drive 26 and modem 28) may be coupled to PCI bus 22. Although only a few basic components of computer system 10 are shown in the figure, many more devices may be included. For example, PCI bus 22 can accommodate up to 32 devices, some of which may be bridges to other buses which may include even more devices.

[0025] Computer system 10 may be configured in a number of ways. Consequently, a number of configuration parameters associated with the hardware and software configurations of the computer system must be set up. These configuration parameters may include various types of information, such as host names, IP addresses, debug options, etc. The configuration parameters will be referred to collectively herein as non-volatile configuration information (NVCI). The NVCI is stored in a persistent storage device such as flash memory 16. This allows the computer system to maintain its configuration through cycles in which the computer system is powered up and powered down.

[0026] Flash memory is non-volatile—when a flash memory device is powered down, it retains the data that is stored in it. Flash memory devices are similar to EPROMS (erasable programmable read only memories,) except that flash memories are electrically erasable (EPROMS are erasable by exposing them to UV light.) It should be pointed but that flash memories have a limited lifetime. That is, they can only be erased a limited number of times. After the maximum number of erasures has been reached the flash memory may no longer operate reliably. It is therefore important to make the most efficient use of flash memories and to minimize the number of times the memory (or a particular segment thereof) is cleared (erased.)

[0027] Referring to FIG. 2, a flow diagram illustrating the method by which the NVCI is accessed is shown. The key-value pairs which form the NVCI are initially stored in the flash memory. When the computer system is booted up or restarted (i.e., at boot time,) the processor reads the key-value pairs from the flash memory into the working memory. As the key-value pairs are read from the flash memory, they are inserted into a hash table. During normal operation of the computer system, the configuration parameters which are needed are read from the hash table. Thus, the system uses relatively inexpensive flash memories for persistent storage of the NVCI, but at the same time achieves high performance by maintaining a hash table containing the current NVCI values in the working memory.

[0028] The key-value pairs are stored serially in the flash memory, beginning with the oldest (least recent) entry and ending with the most recent entry. (“Entry” is used here to refer to a particular occurrence of a key-value pair and associated data.) The least recent entry is normally located at the lowest address, while the most recent entry is normally located at the highest address. The manner in which the entries are stored in the flash memory is shown graphically in FIG. 3. In one embodiment, the flash memory is segmented, and the first key-value pair is stored at the lowest address of an “active” (i.e., currently used) segment of the flash memory. The lowest memory address in FIG. 3 is therefore indicated as “base+0”. The entries are stored in contiguous locations, with no unused memory between succeeding entries. One or more entries may each contain the same key—the entry having the highest address in the flash memory will contain the most recent value corresponding to the key. (It should be noted that this may not be true for some implementations which use more than one segment of a segmented flash memory, but will be true within each segment.) As can be seen from the figure, entries containing key-value pairs of varying lengths can be accommodated without difficulty.

[0029] The serial storage of the key-value pairs in the flash memory provides flexibility in handling the different configuration parameters in the NVCI. Unlike convention fixed format storage of configuration parameters, the serial storage scheme easily handles dynamic data types. Further, this scheme has advantages over systems which use tables of contents and pointers to store configuration parameters having dynamic data types. Since the configuration parameters are serially logged in the flash memory, the complicated algorithms required for space allocation in table-of-contents systems are avoided. Because the use of pointers is eliminated, bugs relating to pointer manipulation are also avoided.

[0030] In the embodiment depicted in FIG. 3, each entry in the flash memory consists not only of key 41 and value 42, but also key size 43, value size 44 and checksum 45. Key size 43 and value size 44 facilitate reading of the key-value pairs from the flash memory. Key size 43 immediately precedes key 41 and indicates the amount of memory occupied by key 41 in bytes. Value size 44 immediately precedes value 42 and indicates the number of bytes of the flash memory which are required to store value 42. Checksum 45 is a fixed-length checksum which is used to detect errors in the remainder of the entry.

[0031] When the computer system boots up (or restarts,) it constructs a hash table in the working memory. The hash table is used to store a working copy of the NVCI. As each NVCI entry is read from the flash memory, its key is hashed and the value is placed in the corresponding location in the hash table. When a value has already been stored in the hash table for a particular key and a subsequent entry for that same key is read, the value in the second entry displaces the value which was contained in the first entry. Thus, the most recently read value corresponding to each key is stored in the hash table. Since the flash memory is read in the same order it was written (i.e., from the lowest address to the highest,) the most recent value for each of the keys stored in the flash memory is also stored in the hash table (while obsolete values are discarded.)

[0032] During runtime, it may be necessary for the computer system to read the NVCI to determine the system's configuration, or simply to provide one of the configuration parameters to a process or device. The appropriate configuration parameters are retrieved from the hash table in the working memory. Since the hash table includes the most recent entries for each of the configuration parameters included in the NVCI, there is no need to access the flash memory. Read accesses of the NVCI are therefore made without any degradation of the performance of the computer system.

[0033] It may also be necessary during runtime to update the configuration of the computer system. Changes to the configuration are recorded by updating the corresponding parameter in the NVCI. Therefore, when a new configuration is stored, new key-value pairs indicating the changes are stored in the hash table. The new values of the key-value pairs replace the old values so that the hash table contains only the current value for each key. This is shown graphically in FIG. 4. This figure depicts a hash table 50 and a series of entries 51-55. Each entry comprises a key and a corresponding value. When a particular configuration parameter is updated, the corresponding key and value (key 2 and value 2′ in the figure) are inserted into the hash table. The new value (value 2′) replaces the old value (value 2) in the table, so that each key in the table only has one corresponding value.

[0034] Because the hash table is stored in the working memory, which is not a persistent storage means, storing the updated values in the hash table alone is not sufficient to ensure that the system configuration will be stored through a power cycle (i.e., when the computer system is powered down and powered back up,) a reset or a similar event. The new key-value pairs are therefore also written through to the flash memory, which is a persistent storage device. While write accesses to the flash memory may not be completed quickly, this does not degrade the performance of the computer system since configuration parameters are read from the hash table when needed. The write accesses to the flash memory can therefore proceed in the background without causing the processor to wait. Moreover, when a configuration parameter changes and needs to be written to the flash memory, only the changed parameter is written—there is no need to write those configuration parameters which have not changed to the flash memory.

[0035] When a configuration parameter is written to the flash memory, it does not physically replace a previously stored value of the parameter. Instead, a corresponding key-value pair is written to the next available location in the flash memory. This is shown graphically in FIG. 5. It can be seen from this figure that the key-value pairs are serially stored in contiguous memory locations and are not overwritten. The presence of several entries for the same key does not raise ambiguity as to the current value corresponding to the key, because the computer system does not read any of the entries from the flash memory at runtime—they are only read at boot-up (or restart) to initialize the hash table, and then the current (most recently stored) value for each key is the only one which is not overwritten. (It should be noted that, while only the keys and corresponding values of the key-value pair entries are shown in FIG. 5, the entries may include other information, such as the data sizes and checksums shown in FIG. 3. Also, although the key-value pairs are shown as pairs 1, 2 . . . N, they need not be stored in any particular order.)

[0036] Because updates to the computer system's configuration parameters are appended to the existing NVCI entries in the flash memory, the memory is gradually filled up as updates are made to the configuration parameters. Even though the number of configuration parameters, hence the number of key-value pairs, used by the computer system may remain fixed, the number of obsolete entries in the flash memory will grow. When the flash memory is filled, or when a predetermined threshold capacity is reached, the flash memory must somehow be refreshed so that additional modifications to the configuration parameters can be stored.

[0037] In the case of a single conventional flash memory, the current configuration parameters have to be stored in a location other than the flash memory while the flash memory is erased. The current configuration parameters are then written back to a series of contiguous locations in the flash memory, beginning with the lowest address. Since the obsolete entries are not written back to the flash memory, this has the same effect as if only the obsolete entries were erased and the current entries were condensed and moved the lowest addresses in the flash memory.

[0038] If the configuration parameters are stored only in the hash table in the working memory (which is not persistent,) this information could be lost if the computer system were powered down or reset before the configuration parameters were written back to the flash memory. Therefore, in a preferred embodiment, the NVCI is stored in a segmented flash memory. A segmented flash memory is divided into several chunks, or segments, which can be independently erased. (A conventional flash memory, on the other hand, is only erasable in its entirety.) The segmented flash memory is used in essentially the same way as the conventional flash memory, but each segment is, for the most part, handled as a small, independent flash memory. When an active segment is filled, however, the NVCI can be written to another segment which has already been erased. The second segment can then be made the active segment. This process can be repeated when the second segment is filled. The next segment to be used as the active segment can be selected in round-robin fashion, or the least recently used inactive segment may be selected. Thus, the risk of losing the configuration parameters while the flash memory is being refreshed is avoided. (It should be noted that this advantage may also be provided in a system which employs more than one flash memory to store the NVCI.)

[0039] Another advantage of segmented flash memory is that, if the NVCI is confined to a single segment of the flash memory, it may take less time to read the NVCI into the working memory at startup. Immediately after each type of flash memory has been cleared, reading the NVCI into working memory will take the same amount of time in either case, because both the segmented and conventional flash memories contain the same amount of data. Once the NVCI has filled the current segment in a segmented flash memory, however, the current entries are copied into a new segment so that only a minimal amount of space is occupied in the new (now current) segment. In the conventional flash memory, on the other hand, the NVCI (including obsolete entries) takes up space which is at least the equivalent of an entire segment. In other words, the non-segmented flash memory has not been cleared, so it still contains the obsolete data. Because there is less data to read in the segmented memory, it will take less time to read the NVCI from it than from the conventional flash memory. (It should be noted that, although the segmented flash memory is cleared more often, only one segment at a time is cleared, so the lifetime of the segmented flash memory is not diminished any more quickly than the conventional flash memory.)

[0040] While the description above is directed primarily to embodiments in which the NVCI is stored in a single segment of the flash memory, it is contemplated that more than one segment may be active at the same time. For example, it may be desirable to maintain isolated sets of configuration parameters. In one embodiment, a computer system may use a first group of configuration parameters which are updated infrequently and a second group of configuration parameters which are updated more often. If the first group of configuration parameters is maintained in a separate segment of the flash memory, it will fill up more slowly than the segment containing the second group of parameters and will have to be recopied and erased less frequently than the segment containing the second group. The overall number of erasures of the segments will therefore be reduced and the lifetime of the flash memory extended.

[0041] While the present invention has been described with reference to particular embodiments, it will be understood that the embodiments are illustrative and that the invention scope is not limited to these embodiments. Many variations, modifications, additions and improvements to the embodiments described are possible. These variations, modifications, additions and improvements may fall within the scope of the invention as detailed within the following claims.