Methods and apparatus for allocating memory

• US 20050071595A1
• Filed: 09/25/2003
• Published: 03/31/2005
• Est. Priority Date: 09/25/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thompson, Jason A., Steenburgh, James A., Irish, John D., Ouda, Ibrahim A.
• Application Number:
  US10/670,703
• Publication Number:
  US 20050071595A1
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

In a first aspect, a first method is provided. The first method includes the steps of (1) receiving a set of data; (2) determining whether a free group entry of a size required by a portion of the set of data exists in one of a plurality of sections of a memory; (3) if a free group entry of the size required by the portion of the set of data does not exist in one of the plurality of sections of the memory, determining whether the memory includes one or more sections of an unallocated size; and (4) if the memory includes one or more sections of an unallocated size, allocating one of the sections of an unallocated size to the size required by the portion of the set of data thereby creating a section of a dynamically allocated size. Numerous other aspects are provided.

Claims

1. A method comprising:

receiving a set of data;

determining whether a free group entry of a size required by a portion of the set of data exists in one of a plurality of sections of a memory;

if a free group entry of the size required by the portion of the set of data does not exist in one of the plurality of sections of the memory, determining whether the memory includes one or more sections of an unallocated size; and

if the memory includes one or more sections of an unallocated size, allocating one of the sections of an unallocated size to the size required by the portion of the set of data thereby creating a section of a dynamically allocated size, the section of the dynamically allocated size including one or more group entries of the size required by the portion of the set of data.

2. The method of claim 1 wherein determining whether a free group entry of the size required by the portion of the set of data exists in one of a plurality of sections of the memory includes determining whether a free group entry of the size required by the portion of the set of data for uniquely identifying each portion of the set of data exists in one of the plurality of sections of memory.

3. The method of claim 1 wherein determining whether the memory includes one or more sections of an unallocated size includes accessing a control structure for one or more sections of the memory, the control structure storing information about the structure of a section.

4. The method of claim 1 further comprising, from the section of a dynamically allocated size, allocating an initial group entry of the size required by the portion of the set of data for storing the portion of the set of data.

5. The method of claim 4 further comprising:

receiving a modified set of data;

determining whether a portion of the modified set of data may be stored more efficiently in a group entry of a different size from another section of the memory such that the aggregate number of unused entries in the group entries used for storing the modified set of data is minimized;

allocating a group entry of the different size required by the portion of the modified set of data from another section of the memory to store the portion of the modified set of data; and

deallocating the initial group entry to the section of memory from which the initial group entry was allocated.

6. The method of claim 5 further comprising updating the control structure that stores information about the structure of the other section.

7. The method of claim 5 further comprising updating the control structure that stores information about the structure of the section of memory from which the initial group entry was allocated.

8. The method of claim 5 wherein deallocating the initial group entry to the section of memory from which the initial group entry was allocated leaves all entries of the section unused.

9. The method of claim 8 further comprising clearing the group entry size allocation of the section.

10. The method of claim 1 further comprising, if the memory does not include one or more sections of an unallocated size, determining whether a free group entry of a size larger than the size required by the portion of the data exists, wherein sections allocated to the smallest available size larger than the size required by the portion of the data are checked prior to sections allocated to larger available sizes.

11. The method of claim 10 further comprising, if a free group entry of a size larger than the size required by the portion of the data exists in a section allocated to a size larger than the size required by the portion of data, allocating an initial group entry of the size larger than the size required by the portion of the set of data from the section allocated to a size larger than the size required by the portion of the data for storing the portion of the set of data.

12. The method of claim 10 further comprising, if a free group entry of a size larger than the size required by the portion of the data does not exist outputting an error condition.

13. The method of claim 11 further comprising:

receiving a modified set of data;

determining whether a portion of the modified set of data may be stored more efficiently in an group entry of a different size from another section of the memory such that the aggregate number of unused entries in the group entries used for storing the modified set of data is minimized;

allocating a group entry of the different size required by the portion of the modified set of data from another section of the memory to store the portion of the modified set of data; and

deallocating the initial group entry to the section of memory from which the initial group entry was allocated.

14. The method of claim 13 further comprising updating the control structure that stores information about the structure of the other section.

15. The method of claim 13 further comprising updating the control structure that stores information about the structure of the section of memory from which the initial group entry was allocated.

16. The method of claim 13 wherein deallocating the initial group entry to the section of memory from which the initial group entry was allocated leaves all entries of the section unused.

17. The method of claim 16 further comprising clearing the group entry size allocation of the section.

18. An apparatus comprising:

a memory;

a plurality of registers; and

dynamic allocation logic coupled to the memory and the plurality of registers, and adapted to;

receive a set of data;

determine whether a free group entry of a size required by a portion of the set of data exists in one of a plurality of sections of the memory;

if a free group entry of the size required by the portion of the set of data does not exist in one of the plurality of sections of the memory, determine whether the memory includes one or more sections of an unallocated size; and

if the memory includes one or more sections of an unallocated size, allocate one of the sections of an unallocated size to the size required by the portion of the set of data thereby creating a section of a dynamically allocated size.

19. The apparatus of claim 18 wherein the dynamic allocation logic is further adapted to determine whether a free group entry of the size required by the portion of the set of data for uniquely identifying each portion of the set of data exists in one of the plurality of sections of memory.

20. The apparatus of claim 18 wherein the dynamic allocation logic is further adapted to access a control structure for one or more sections of the memory, the control structure storing information about the structure of a section.

21. The apparatus of claim 18 wherein the dynamic allocation logic is further adapted to, from the section of a dynamically allocated size, allocate an initial group entry of the size required by the portion of the set of data for storing the portion of the set of data.

22. The apparatus of claim 21 wherein the dynamic allocation logic is further adapted to:

receive a modified set of data;

determine whether a portion of the modified set of data may be stored more efficiently in a group entry of a different size from another section of the memory such that the aggregate number of unused entries in the group entries used for storing the modified set of data is minimized;

allocate a group entry of the different size required by the portion of the modified set of data from another section of the memory to store the portion of the modified set of data; and

deallocate the initial group entry to the section of memory from which the initial group entry was allocated.

23. The apparatus of claim 22 wherein the dynamic allocation logic is further adapted to update the control structure that stores information about the structure of the other section.

24. The apparatus of claim 22 wherein the dynamic allocation logic is further adapted to update the control structure that stores information about the structure of the section of memory from which the initial group entry was allocated.

25. The apparatus of claim 22 wherein the dynamic allocation logic is further adapted to deallocate the initial group entry to the section of memory from which the initial group entry was allocated leaving all entries of the section unused.

26. The apparatus of claim 25 wherein the dynamic allocation logic is further adapted to clear the group entry size allocation of the section.

27. The apparatus of claim 18 wherein the dynamic allocation logic is further adapted to, if the memory does not include one or more sections of an unallocated size, determine whether a free group entry of a size larger than the size required by the portion of the data exists, wherein sections allocated to the smallest available size larger than the size required by the portion of the data are checked prior to sections allocated to larger available sizes.

28. The apparatus of claim 27 wherein the dynamic allocation logic is further adapted to, if a free entry group of a size larger than the size required by the portion of the data exists in a section allocated to a size larger than the size required by the portion of data, allocate an initial group entry of the size larger than the size required by the portion of the set of data from the section allocated to a size larger than the size required by the portion of the data for storing the portion of the set of data.

29. The apparatus of claim 27 wherein the dynamic allocation logic is further adapted to, if a free group entry of a size larger than the size required by the portion of the data does not exist, output an error condition.

30. The apparatus of claim 23 wherein the dynamic allocation logic is further adapted to:

receive a modified set of data;

determine whether a portion of the modified set of data may be stored more efficiently in a group entry of a different size from another section of the memory such that the aggregate number of unused entries in the group entries used for storing the modified set of data is minimized;

allocate a group entry of the different size required by the portion of the modified set of data from another section of the memory to store the portion of the modified set of data; and

deallocate the initial group entry to the section of memory from which the initial group entry was allocated.

31. The apparatus of claim 30 wherein the dynamic allocation logic is further adapted to update the control structure that stores information about the structure of the other section.

32. The apparatus of claim 30 wherein the dynamic allocation logic is further adapted to update the control structure that stores information about the structure of the section of memory from which the initial group entry was allocated.

33. The apparatus of claim 30 wherein the dynamic allocation logic is further adapted to deallocate the initial group entry to the section of memory from which the initial group entry was allocated leaving all entries of the section unused.

34. The apparatus of claim 33 wherein the dynamic allocation logic is further adapted to clear the group entry size allocation of the section.