Dynamic allocation of computer memory

• US 7,058,788 B2
• Filed: 01/17/2002
• Issued: 06/06/2006
• Est. Priority Date: 02/23/2001
• Status: Active Grant

• Current Assignee: FalconStor, Inc (Hale Capital Management LP)
• Original Assignee: Falconstor Software Incorporated (Hale Capital Management LP)
• Inventors: Louie, Larry, Niles, Ronald Steven
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): BAKER, PAUL A
• Application Number:
  US10/052,208
• Publication Number:
  US 20030135709A1
• Time in Patent Office: 1,601 Days
• Field of Search: 711202-209, 711/220, 711/221
• US Class Current: 711/220
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

A method for processing requests or commands for writing and reading to and from memory that has not been allocated and reserved for one or more volumes, and a method for establishing one or more volumes, where the one or more volumes define an area of the memory that is accumulatively greater than the actual memory capacity, thus allowing for memory to be added at a later time.

Claims

1. A method for writing data to a memory having physical sector addresses that have not been assigned to logical sector addresses, the method comprising:

receiving a write command having associated therewith a starting logical sector address;

assigning the starting logical sector address to a group of the physical sector addresses;

assigning the group of the physical sector addresses to a group of logical sector addresses;

determining from the group of the physical sector addresses a physical sector address associated with the starting logical sector address; and

writing data to the physical sector address within the group of the physical sector addresses associated with the starting logical sector address.

2. The method of claim 1 wherein the write command has associated therewith a write sector count, the group of the physical sector addresses having a physical starting sector address and a sector count, and the group of logical sector addresses having a group starting logical sector address.

3. The method of claim 2 wherein the determining from the group of the physical sector addresses comprises:

determining a value by subtracting the group starting logical sector address from the starting logical sector address; and

determining a second value by adding the value to the physical starting sector address.

4. The method of claim 2 further comprising:

determining whether the write sector count exceeds an amount of physical sector addresses available within the group of the physical sector addresses;

if it does, determining a second starting logical sector address;

assigning the second starting logical sector address to a second group of the physical sector addresses; and

assigning the second group of the physical sector addresses to a second group of logical sector addresses.

5. The method of claim 4 wherein the determining whether the write sector count exceeds an amount of physical sector addresses available further comprises:

adding the physical starting sector address to the sector count producing a third value;

subtracting the second value from the third value producing a fourth value; and

comparing the fourth value to the write sector count, if the write sector count is greater than the fourth value, then the write sector count exceeds an amount of physical sector addresses available.

6. The method of claim 1 further comprising determining whether an amount of data written to the group of the physical sector addresses exceeds a predefined amount.

7. The method of claim 6 further comprising indicating that the amount of data written to the group of the physical sector addresses exceeds the predefined amount, if the amount of data written to the group of the physical sector addresses exceeds the predefined amount.

8. A system for processing data comprising:

a memory having physical sector addresses that have not been assigned to logical sector addresses; and

a processor configured to;

receive a write command having associated therewith a starting logical sector address;

assign the starting logical sector address to a group of the physical sector addresses;

assign the group of the physical sector addresses to a group of logical sector addresses;

determine from the group of the physical sector addresses a physical sector address associated with the starting logical sector address; and

write data to the physical sector address within the group of the physical sector addresses associated with the starting logical sector address.

9. The system of claim 8 wherein:

the write command has associated therewith a write sector count;

the group of the physical sector addresses has a physical starting sector address and a sector count; and

the group of logical sector addresses has a group starting logical sector address.

10. The system of claim 9 wherein the processor is configured to determine from the group of the physical sector addresses a physical sector address by:

determining a value by subtracting the group starting logical sector address from the starting logical sector address; and

determining a second value by adding the value to the physical starting sector address.

11. The system of claim 9 wherein the processor is further configured to:

determine whether the write sector count exceeds an amount of physical sector addresses available within the group of the physical sector addresses;

if it does, determine a second starting logical sector address;

assign the second starting logical sector address to a second group of the physical sector addresses; and

assign the second group of the physical sector addresses to a second group of logical sector addresses.

12. The system of claim 11 wherein the processor is configured to determine whether the write sector count exceeds an amount of physical sector addresses available by:

adding the physical starting sector address to the sector count producing a third value;

subtracting the second value from the third value producing a fourth value; and

comparing the fourth value to the write sector count,

if the write sector count is greater than the fourth value, then the write sector count exceeds an amount of physical sector addresses available.

13. The system of claim 8 wherein the processor is further configured to determine whether an amount of data written to the group of the physical sector addresses exceeds a predefined amount.

14. The method of claim 13 wherein the processor is further configured to indicate that the amount of data written to the group of the physical sector addresses exceeds the predefined amount, if the amount of data written to the group of the physical sector addresses exceeds the predefined amount.

15. A method for processing a request or command, having a starting logical sector address, to write data to a memory, where the memory has not been allocated and reserved, the method comprising:

grouping physical sector addresses into a plurality of segments;

reading the starting logical sector address;

selecting a segment from the plurality of segments;

associating the segment and physical sector addresses associated therewith, with the starting logical sector address and a plurality of logical sector addresses;

determining a physical sector address associated with the starting logical sector address; and

writing the data in the memory at the physical sector address.

16. The method of claim 15 further comprising setting an indicator indicating that the segment is selected.

17. The method of claim 15 further comprising setting an indicator indicating that the segment and associated plurality of logical sector addresses are associated with the starting logical sector address.

18. The method of claim 15 wherein the segment has a starting logical segment address, and associated therewith a starting physical sector addresses associated with the segment includes a starting physical sector address, the determining the physical sector address further comprising:

subtracting the starting logical segment address from the starting logical sector address producing a result; and

adding the result with the starting physical sector address.

19. A system for processing a data write request or command, having a starting logical sector address, comprising:

a memory that has not been allocated and reserved; and

a processor configured to;

group physical sector addresses into a plurality of segments;

read the starting logical sector address;

select a segment from the plurality of segments;

associate the segment and physical sector addresses associated therewith, with the starting logical sector address and a plurality of logical sector addresses;

determine a physical sector address associated with the starting logical sector address; and

write the data in the memory at the physical sector address.

20. The system of claim 19 wherein the processor is further programmed to set an indicator indicating that the segment is selected.

21. The system of claim 19 wherein the processor is further configured to set an indicator indicating that the segment and associated plurality of logical sector addresses are associated with the starting logical sector address.

22. The system of claim 19 wherein:

the segment has a starting logical segment address, and associated therewith a starting physical sector addresses associated with the segment includes a starting physical sector address;

the processor being further configured to determine the physical sector address by;

subtracting the starting logical segment address from the starting logical sector address producing a result; and

adding the result with the starting physical sector address.

23. A method for processing a request or command, having a starting logical sector address, to write data to a memory, where the memory has not been allocated and reserved and is represented as a plurality of segments, the method comprising:

reading the starting logical sector address;

selecting a first segment from the plurality of segments;

selecting a first set of physical sector addresses;

associating the first segment and the first set of physical sector addresses to the starting logical sector address;

associating the first set of physical sector addresses with a set of logical sector addresses;

determining a physical sector address associated with the starting logical sector address;

determining a quantity of physical sectors available within the first segment;

determining whether the data exceeds the quantity of physical sectors;

if the data exceeds the quantity of physical sectors, selecting a second segment from the plurality of segments;

selecting a second set of physical sector addresses;

associating the second segment and the second set of physical sector addresses to a second starting logical sector address;

associating the second set of physical sector addresses with a second set of logical sector addresses;

determining a second physical sector address associated with the second starting logical sector address; and

writing the data in the memory at the first set of physical sector addresses and the second set of physical sector addresses.

24. A method for processing a request or command, having a starting logical sector address and a sector count, to write to a memory, where one or more segments having a predetermined number of logical sector addresses has been allocated and reserved for the memory, the method comprising:

determining whether the starting logical sector address is within a segment of the one or more segments;

if the starting logical sector address is within a segment of the one or more segments, determining the segment that the starting logical sector address is within;

determining whether the sector count exceeds the predetermined number of logical sector addresses in the segment that are available;

if the sector count does not exceed the predetermined number of logical sector addresses in the segment that are available, writing to the predetermined number of logical sector addresses in the segment that are available;

if the sector count does exceed the predetermined number of logical sector addresses in the segment that are available,

writing data to the predetermined number of logical sector addresses in the segment that are available,

determining a second starting logical sector address and a second sector count, and

determining whether the second starting logical sector address is within a second segment of the one or more segments; and

if the second starting logical sector address is within the second segment of the one or more segments, writing data to the predetermined number of logical sector addresses in the second segment that are available.

25. A method for processing a request or command, having a starting logical sector address, to read data from a memory, the method comprising:

reading the starting logical sector address;

determining whether the starting logical sector address is associated with a segment descriptor;

if the starting logical sector address is not associated with the segment descriptor, then generating data and respond to the request or command by returning the generated data; and

if the starting logical sector address is associated with the segment descriptor, then reading the data associated with the segment descriptor from the memory.

26. The method of claim 25 wherein the determining step comprises searching a table for a segment descriptor having a logical sector address range that is associated with the starting logical sector address.

27. The method of claim 25 wherein the step of reading the data associated with the segment descriptor comprises:

reading a physical starting sector address and a sector count from the segment descriptor; and

determining which physical sector addresses to read the data.

28. A system for processing a request or command, having a starting logical sector address, to read data from a memory, the system comprising:

a memory for storing data; and

a processor configured to;

read the starting logical sector address;

determine whether the starting logical sector address is associated with a segment descriptor;

if the starting logical sector address is not associated with the segment descriptor, then generate data and respond to the request or command by returning the generated data; and

if the starting logical sector address is associated with the segment descriptor, then read the data associated with the segment descriptor from the memory.

29. The system of claim 28 wherein the processor is configured to determine whether the starting logical sector address is associated with a segment descriptor by searching a table for a segment descriptor having a logical sector address range that is associated with the starting logical sector address.

30. The system of claim 28 wherein the processor is configured to read the data associated with the segment descriptor by:

reading a physical starting sector address and a sector count from the segment descriptor; and

determining which physical sector addresses to read the data.

31. A method for processing a request or command, having a starting logical sector address and a sector count value, to read data from a memory, the method comprising:

reading the starting logical sector address;

determining whether the starting logical sector address is associated with a segment descriptor;

if the starting logical sector address is not associated with the segment descriptor, then generating data and respond to the request or command by returning the generated data; and

if the starting logical sector address is associated with the segment descriptor, then reading the data from a location in memory that is associated with the starting logical sector address and the sector count value, as defined by the segment descriptor.

32. The method of claim 31 wherein the determining step comprises searching a table for a segment descriptor having a logical sector address range that is associated with the starting logical sector address.

33. The method of claim 31 wherein the step of reading the data from a location in memory comprises:

reading a physical starting sector address and a sector quantity from the segment descriptor;

determining physical sector addresses defined by the association of the starting logical sector address and the sector count value with the physical starting sector address and the sector quantity from the segment descriptor; and

reading the data located in memory at the physical sector addresses.

34. A system for processing a request or command, having a starting logical sector address and a sector count value, to read data from a memory, the system comprising:

a memory for storing data; and

a processor configured to;

read the starting logical sector address;

determine whether the starting logical sector address is associated with a segment descriptor;

if the starting logical sector address is not associated with the segment descriptor, then generate data and respond to the request or command by returning the generated data; and

if the starting logical sector address is associated with the segment descriptor, then read the data from a location in memory that is associated with the starting logical sector address and the sector count value, as defined by the segment descriptor.

35. The system of claim 34 wherein the processor is configured to determine whether the starting logical sector address is associated with a segment descriptor by searching a table for a segment descriptor having a logical sector address range that is associated with the starting logical sector address.

36. The system of claim 34 wherein the processor is configured to read the data from a location in memory by:

reading a physical starting sector address and a sector quantity from the segment descriptor;

determining physical sector addresses defined by the association of the starting logical sector address and the sector count value with the physical starting sector address and the sector quantity from the segment descriptor; and

reading the data located in memory at the physical sector addresses.