Patent Publication Number: US-7725646-B2

Title: Method of using a flash memory for a circular buffer

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   This invention relates generally to a flash memory for a circular buffer. 
   2. Description of Related Art 
   One form of computer memory is non-volatile memory. An example of non-volatile memory is flash memory. One use of memory, including non-volatile memory such as flash memory, is to store log data. However, there is a need for a flash memory able to be used in a circular buffer. 
   The foregoing objects and advantages of the invention are illustrative of those that can be achieved by the various exemplary embodiments and are not intended to be exhaustive or limiting of the possible advantages which can be realized. Thus, these and other objects and advantages of the various exemplary embodiments will be apparent from the description herein or can be learned from practicing the various exemplary embodiments, both as embodied herein or as modified in view of any variation which may be apparent to those skilled in the art. Accordingly, the present invention resides in the novel methods, arrangements, combinations and improvements herein shown and described in various exemplary embodiments. 
   SUMMARY OF THE INVENTION 
   In light of the present need for a flash memory for a circular buffer, a brief summary of various exemplary embodiments is presented. Some simplifications and omission may be made in the following summary, which is intended to highlight and introduce some aspects of the various exemplary embodiments, but not to limit its scope. Detailed descriptions of a preferred exemplary embodiment adequate to allow those of ordinary skill in the art to make and use the invention concepts will follow in later sections. 
   Various exemplary embodiments are a method of using a FLASH memory for a circular buffer, including one or more of the following according to various combinations: providing a circular buffer having a plurality of sectors; designating a byte of data of each of the plurality of sectors of the circular buffer as a binary state indicator; setting the binary state indicator for each of the plurality of sectors to empty; setting the binary state indicator for a first of the plurality of sectors to last; writing data to the first of the plurality of sectors; setting the binary state indicator for a second of the plurality of sectors to last and setting the binary state indicator for the first of the plurality of sectors to first; writing data to the second of the plurality of sectors; setting the binary state indicator for the second of the plurality of sectors to middle and setting the binary state indicator for a third of the plurality of sectors to last; and writing data to the third of the plurality of binary sectors. 
   Various exemplary embodiments are methods of using a FLASH memory for a circular buffer, including one or more of the following according to various combinations: setting the binary state indicator for the third of the plurality of sectors to middle and the binary state indicator for the first of the plurality of sectors to erase and then last; setting the binary state indicator for the second of the plurality of sectors to first; and writing data to the first of the plurality of sectors a second time. 
   Various exemplary embodiments are a method of using a FLASH memory for a circular buffer, including one or more of the following: setting the binary state indicator for the first of the plurality of sectors to middle; setting the binary state indicator for the second of the plurality of sectors to erase and then last; setting the binary state indicator for the third of the plurality of sectors to first; and writing data to the second of the plurality of sectors a second time. 
   Various exemplary embodiments are a method of using a FLASH memory for a circular buffer, including one or more of the following according to various combinations: the binary state indicators comprise 8 bits of data of FLASH memory; the erase binary state indicator corresponds to a binary number FF; the binary state indicator indicating the last sector corresponds to a binary number FA; the binary state indicator indicating the middle sector corresponds to a binary number F0; and the binary state indicator indicating the first sector corresponds to a binary number A0. 
   Various exemplary embodiments are a method of using a FLASH memory for a circular buffer, including one or more of the following according to various combinations: providing a plurality of sectors of FLASH memory in a circular buffer; designating one byte of data of each of the plurality of sectors of FLASH memory in the circular buffer as a binary state indicator; saving data sequentially in the circular buffer; and cycling through a plurality of sectors of the binary state indicators as the data is sequentially saved in the circular buffer. 
   Various exemplary embodiments are a FLASH memory for use in a circular buffer and implementing any of the embodiments of the method. Thus, various exemplary embodiments include a plurality of sectors of FLASH memory, each sector of FLASH memory including a pre-determined number of bits designated as a binary state indicator, wherein the binary state indicators transition through a plurality of states in connection with an operation of the circular buffer. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein: 
       FIG. 1  is a schematic diagram of an exemplary embodiment of a circular buffer; 
       FIG. 2  is a schematic diagram of exemplary binary state indicators; and 
       FIG. 3  is a schematic diagram of an exemplary embodiment of a flash memory for a circular buffer. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE INVENTION 
   A need exists for a reliable and efficient approach to storing line card data log information. Line card data log information includes, but is not limited to, start up information, hardware revision numbers, software revision numbers, especially for software downloaded through the Internet, diagnostic failure information, and so on. 
   In other words, there is a need for a reliable and efficient approach to storing any information that is useful for a root cause analysis on returned line cards. Some embodiments of line cards have stored fixed sized records of logged data in a circular log buffer. Some embodiments of such circular log buffers include eight 64 KB sectors of 512 KB FLASH memory. However, a problem with such embodiments is that the implementation of fixed sized records is a waste of memory space. This is true because log data records are variable in length. The length of log data records depends on the type of data being logged. 
   Thus, efficient use of FLASH memory for data logging is advantageous. This is true because the FLASH memory is often used for other purposes on the line card. For example, some embodiments of a line card use FLASH memory for boot software. 
   Additionally, in many implementations, a line card is in a system for an extended period of time and logs a significant amount of data before it becomes necessary to read back the logged data. Thus, it is believed to be important that a given size circular buffer stores as much log data as possible. 
   A typical FLASH memory can only be written to once. Afterwards, a typical FLASH memory must be erased and re-initialized before it can be written to again. This property of FLASH memory makes FLASH memory problematic in data logging applications. 
   Further, typically, the minimum unit of FLASH memory that can be erased is a sector of memory. Typically, the erasure of memory constitutes the resetting of bits in the memory to binary 1s. In other words, when a bit of FLASH memory is written to by setting it to 0 the entire sector of memory to which that bit of memory belongs must be erased in order set any particular bit to a 1 again. 
   In order to overcome the forgoing problems, various exemplary embodiments create a circular buffer for data logging that uses fixed size sectors of FLASH memory. In various exemplary embodiments, the record length is variable. In various exemplary embodiments, the record length is written in a length, value (LV) format. In various exemplary embodiments, the first byte in each sector of memory indicates a status of the sector in the circular buffer. 
   In various exemplary embodiments, the status of each sector in a circular buffer is one of four possibilities. The four possibilities include empty or erase (E), last (L), middle (M) and first (F). Using the forgoing status indicators in each sector of memory in a circular buffer, the head and tail of the circular buffer may easily identified. 
   The easy identification of the head and tail of a circular buffer enable easier data retrieval from that circular buffer. Further, an easy identification of the head and tail in a circular buffer enables the resuming of data logging at a correct location in the circular buffer in the case of a line card re-boot. Based on the foregoing, various exemplary embodiments efficiently overcome limitations associated with the unique properties of a FLASH memory that limit the FLASH memory to writing once and then resetting, re-initializing, or erasing. 
   Referring now to the drawings, in which like numerals refer to like components or steps, there are disclosed broad aspects of various exemplary embodiments. 
     FIG. 1  is a schematic diagram of an exemplary embodiment of a circular buffer  100 . The exemplary circular buffer  100  includes four sectors. 
   The first sector of exemplary circular buffer  100  is S 1 . The second sector of exemplary circular buffer  100  is S 2 . The third sector of exemplary circular buffer  100  is S 3 . The fourth sector of exemplary circular buffer  100  is S 4 . 
   The circular buffer  100  proceeds in a circular manner through its four sectors from S 1  to S 2  to S 3  to S 4  and back to S 1 . This is indicated by the arrows in  FIG. 1 . 
   It should be apparent that various exemplary embodiments are implemented in circular buffers having any number of sectors. Exemplary circular buffer  100  is depicted in order to illustrate the concepts as implemented in various exemplary embodiments having a circular buffer size of more or less than four sectors. This will be described in greater detail below. 
     FIG. 2  is a schematic diagram  200  including exemplary binary state indicators. Each binary state indicator consists of eight bits. When a FLASH memory is erased or re-initialized, and all of its bits are set to 1, this is indicated by binary state indicator FF and corresponds to the empty (E) state. 
   After the empty (E) state, in various exemplary embodiments, the sixth and eight bits of the 8 bit binary state indicator are written to the zero value. This corresponds to binary state indicator FA and is used in various exemplary embodiments to represent the last (L) state. 
   Following the last (L) state, in various exemplary embodiments, the fifth and seventh bits of the 8 bits in the binary state indicator are written to zero. This corresponds to binary state F0 or the middle (M) state. 
   Following the middle (M) state, in various exemplary embodiments, the second and fourth bits of the 8 bit binary state indicator are written to the zero value. This corresponds to binary state indicator A0 or the first (F) state. 
   Following the first (F) state, the binary state indicator is erased or re-initialized so that all of its bits are reset to 1 values. This corresponds to binary state indicator FF, the empty (E) state. In various exemplary embodiments, when new logged data exists for writing to the circular buffer  100 , and not enough free space is available in the various sectors of the circular buffer  100 , then the sector having a binary state indicator marked as first (F) is erased to create more free space. In various exemplary embodiments, when reading logged data, the reading of the data begins in the circular buffer  100  at the sector having the binary state indicator marked first (F) and continues until reaching the sector in the circular buffer  100  having a binary state indicator marked as last (L). 
   The L state indicates the last or most recent sector to be written to in the circular buffer. The F state corresponds to the first or least recent sector written to in the circular buffer. The M state corresponds to a middle sector in the circular buffer between the L state and the F state. Thus, it should be apparent that a circular buffer containing more than four sectors will have more than one sector identified as in a middle state once the entire circular buffer has been used. Also, in various exemplary embodiments where a circular buffer contains only two sectors, in various exemplary embodiments that circular buffer contains only a first and last sectors, and no middle sectors. 
   The E state is a state wherein all the data is erased. That is, all the bits in the sector are 1s. The E state represents a transitory state that occurs before a binary state indicator is put in the L state. 
   Based on the foregoing, and with reference to  FIG. 1 , a sequence of state changes in an exemplary circular buffer  100  is as follows. Initially, S 1 , S 2 , S 3  and S 4  are all in the E state. 
   Data is then written to S 1  and the state of S 1  is set to L. Then, data is written to S 2 , S 1  is full, S 2  is set to L, and S 1  is set to F. 
   Next, data is written to S 3 , S 2  is full, S 2  is set to M, and S 3  is set to L. Then, data is written to S 4 , S 3  is full, S 3  is set to M, and S 4  is set to L. 
   Then, data is written to S 1 , S 4  is full, S 4  is set to M, S 1  is set to E and then L, and S 2  is set to F. Next, data is written to S 3 , S 2  is full, S 2  is set to M, S 3  is set to E and then L, and S 4  is set to F. 
   Subsequently, the sequence of state changes continues in the manner described above. It should be apparent, the exemplary embodiment of state changes according to the sequence described above can be varied to apply to circular buffers having fewer or greater than four sectors. 
     FIG. 3  is a schematic diagram of an exemplary embodiment of a flash memory for a circular buffer  300 . Sector S 1  is depicted having its binary state indicator set to L. Sector S 2  is indicated having its binary state indicator set to F. Sector S 3  is indicated having its binary state indicator set to M. Sector S 4  is indicated also with its binary state indicator set to M. 
   Thus, the binary state indicators described in connection with  FIG. 2  are indicated in the upper left hand corner of each of the four sectors of FLASH memory depicted in exemplary FLASH memory for a circular buffer  300 . Buffers with more than four sectors would have more than two sectors in the M state. 
   The sequence of binary state indicators described above in connection in  FIG. 2  enables various exemplary embodiments incorporating FLASH memory to transition through the states of L, M and F before being erased in state E to be set in the L state again. In various exemplary embodiments, the L state denotes the head of the circular buffer. In various exemplary embodiments, the F state denotes the tail of circular buffer. 
   According to the foregoing, in various exemplary embodiments, once the entire circular buffer is full in all states, the next sector to be written to, that is, the sector currently in the F state, is erased, which places it in the E state, and then set to the L state before data is written to that sector. Subsequently, the next sector is then set to the F state and the sector that was previously in the L state is set to the M state. 
   An exemplary implementation of a sequence of states was described above in connection with  FIG. 1 . In various exemplary embodiments, where the act of erasing or re-initializing a flash memory constitutes the setting of all bits in the memory to 0s, then the sequence of exemplary binary states described above is reversed. Otherwise, the subject matter described above operates in various exemplary embodiments in essentially the same manner where a FLASH memory is erased or re-initialized by setting all bits to 0s. 
   According to the forgoing, various exemplary embodiments enable reusing FLASH memory in a circular buffer. Thus, various exemplary embodiments enable memory usage to increase 10 to 20 times or more. Accordingly, various exemplary embodiments enable the use of a non-volatile memory such as a FLASH memory for logging data. 
   Accordingly, various exemplary embodiments are widely applicable to uses in electronic systems. For example, various exemplary embodiments enable the recovery of a file system when a card is restarted. Broadly put, various exemplary embodiments enable a more efficient use of FLASH memory as compared to embodiments that use fixed record sizes for data logging. 
   Although the various exemplary embodiments have been described in detail with particular reference to certain exemplary aspects thereof, it should be understood that the invention is capable of other different embodiments, and its details are capable of modifications in various obvious respects. As is readily apparent to those skilled in the art, variations and modifications can be affected while remaining within the spirit and scope of the invention. Accordingly, the foregoing disclosure, description, and figures are for illustrative purposes only, and do not in any way limit the invention, which is defined only by the claims.