Sequential block allocation in a memory
A region of memory is logically divided into a number of segments, each of which is logically divided into a number of blocks. Blocks are allocated sequentially. A head pointer and a tail pointer demarcate the section of allocated blocks. As allocated blocks are added, the tail pointer is moved so that it remains at the end of the section of allocated blocks. If the tail pointer is within a threshold distance of the head pointer, then the head pointer is moved from its current position to a new position, and the allocated blocks between the current and new positions are freed (deallocated and/or erased). Thus, writes to the memory can be performed sequentially, and blocks can be freed in advance of when they are actually needed.
1. A computer-readable storage medium having computer-executable instructions for causing a computer system to perform a method comprising:
accessing a memory, wherein a region of said memory is logically divided into a plurality of blocks, wherein a first pointer and a second pointer demarcate a section of said blocks that are allocated, and wherein said first pointer and said second pointer are separate and distinct pointers that point to specific addresses in said region;
allocating additional blocks beginning at said second pointer, wherein if said section of allocated blocks reaches an end of said region then blocks are subsequently allocated beginning at a start of said region;
in response to said allocating, moving said second pointer to a resultant end of said section of allocated blocks such that said second pointer switches its location from subsequent to prior said first pointer in said region; and
if said second pointer is within a threshold distance of said first pointer, then moving said first pointer from a first address to a second address in said region, and freeing allocated blocks that are between said first address and said second address prior to beginning a next write operation to said region, wherein said second address is subsequent to said first address in said region.
2. The computer-readable storage medium of claim 1 wherein said method further comprises:
maintaining a generation count, wherein a first value for said generation count is associated with a block in said region when said block is allocated to a file; and
recording said first value in a data structure that comprises information about said file.
3. The computer-readable storage medium of claim 2 wherein said method further comprises:
incrementing said generation count in response to moving said first pointer;
comparing a current value for said generation count to a first threshold value that is less than or equal to a specified maximum value; and
if said current value is greater than said first threshold value, then removing reference to said first value from said data structure.
4. The computer-readable storage medium of claim 3 wherein said method further comprises, if said generation count reaches said maximum value, then:
setting said generation count to an initial value;
identifying data structures that include generation count values that are greater than a second threshold value, wherein said second threshold value is less than or equal to said first threshold value; and
removing references to said generation count values from said data structures.
5. The computer-readable storage medium of claim 1 wherein said method further comprises:
associating a generation count value with each block in said region; and
in response to moving said first pointer, incrementing a generation count value associated with a block that is between said first address and said second address.
6. The computer-readable storage medium of claim 1 wherein said method further comprises:
associating a generation count value with each block in said region; and
prior to reading a block in said region, comparing a first generation count value for said block to a second generation count value, wherein said first generation count value is a current generation count value for said block, wherein said second generation count value is a generation count value that was recorded when said block was allocated to a file, and wherein data in said block is valid for said file if said first generation count value and said second generation count value are equal.
7. The computer-readable storage medium of claim 1 wherein said freeing comprises erasing blocks between said first address and said second address using a TRIM command.
8. The computer-readable storage medium of claim 1 wherein said freeing comprises copying blocks between said first address and said second address from a first device comprising said memory to a second device in a multi-tier storage system.
9. A computer system comprising:
a processor; and
memory coupled to said processor, wherein a region of said memory is logically divided into a plurality of blocks,
said computer system operable to execute operations comprising:
controlling a head pointer and a tail pointer to demarcate a section of said blocks that are allocated, wherein said head pointer and said tail pointer are separate and distinct pointers that point to specific addresses in said region;
adding allocated blocks to said section beginning at said tail pointer, wherein if said section of allocated blocks reaches an end of said region then said section wraps around to a beginning of said region;
in response to said adding, moving said tail pointer to a resultant end of said section of allocated blocks such that said tail pointer switches its location from subsequent to prior said head pointer in said region; and
if said tail pointer is within a threshold distance of said head pointer, then moving said head pointer from a first address to a second address in said region, and freeing allocated blocks that are between said first address and said second address prior to beginning a next write operation to said region, wherein said second address is subsequent to said first address in said region.
10. The computer system of claim 9 wherein said operations further comprise:
maintaining a generation count, wherein a first value for said generation count is associated with a block in said region when said block is allocated to a file; and
recording said first value in a data structure that comprises information about said file.
11. The computer system of claim 10 wherein said operations further comprise:
incrementing said generation count in response to moving said head pointer;
comparing a current value for said generation count to a first threshold value that is less than or equal to a specified maximum value;
if said current value is greater than said first threshold value, then removing reference to said first value from said data structure; and
if said generation count reaches said maximum value, then:
setting said generation count to an initial value;
identifying data structures that include generation count values that are greater than a second threshold value, wherein said second threshold value is less than or equal to said first threshold value; and
removing references to said generation count values from said data structures.
12. The computer system of claim 9 wherein said memory is implemented using a device selected from the group consisting of: a solid state drive; a thin provisioning array.
13. The computer system of claim 9 wherein said operations further comprise:
associating a generation count value with each block in said region; and
in response to moving said head pointer, incrementing a generation count value associated with a block that is between said first address and said second address.
14. The computer system of claim 9 wherein said operations further comprise:
associating a generation count value with each block in said region; and
prior to reading a block in said region, comparing a first generation count value for said block to a second generation count value, wherein said first generation count value is a current generation count value for said block, wherein said second generation count value is a generation count value that was recorded when said block was allocated to a file, and wherein data in said block is valid for said file if said first generation count value and said second generation count value are equal.
15. A computer-implemented method comprising:
accessing a memory, wherein a region of said memory is logically divided into a plurality of blocks, wherein a head pointer and a tail pointer demarcate a section of said blocks that are allocated, wherein said head pointer and said tail pointer are separate and distinct pointers that point to specific addresses in said region;
allocating additional blocks beginning at said tail pointer, wherein if said section of allocated blocks reaches an end of said region then blocks are subsequently allocated beginning at a start of said region;
in response to said allocating, moving said tail pointer to a resultant end of said section of allocated blocks such that said tail pointer switches its location from subsequent to prior said head pointer in said region;
associating a generation count value with each block in said region; and
prior to reading a block in said region, comparing a first generation count value for said block to a second generation count value, wherein said first generation count value is a current generation count value for said block, wherein said second generation count value is a generation count value that was recorded when said block was allocated to a file, and wherein data in said block is valid for said file if said first generation count value and said second generation count value are equal.
16. The computer-implemented method of claim 15 further comprising, if said tail pointer is within a threshold distance of said head pointer, then moving said head pointer from a first address to a second address in said region, incrementing said current generation count, and freeing allocated blocks that are between said first address and said second address prior to beginning a next write operation to said region, wherein said second address is subsequent to said first address in said region.
17. The computer-implemented method of claim 15 further comprising recording said first generation count value in a data structure that comprises information about said file.
18. The computer-implemented method of claim 15 further comprising:
comparing a current value for said generation count value to a first threshold value that is less than or equal to a specified maximum value; and
if said current value is greater than said first threshold value, then removing reference to said first generation count value from said data structure.
19. The computer-implemented method of claim 18 further comprising, if said generation count reaches said maximum value, then:
setting said generation count value to an initial value;
identifying data structures that include generation count values that are greater than a second threshold value, wherein said second threshold value is less than or equal to said first threshold value; and
removing references to said generation count values from said data structures.
20. The computer-implemented method of claim 15 further comprising incrementing a generation count value associated with a block that is between said first address and said second address.