Method and apparatus for managing large numbers of objects having the same property

• US 20030037060A1
• Filed: 08/14/2001
• Published: 02/20/2003
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kuehnel, Andreas H.
• Granted Patent: US 7,107,299 B2
• Time in Patent Office: Days
• US Class Current: 707/103R
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

The invention is an apparatus and method for managing large numbers of objects having the same property. In various aspects the invention includes an apparatus for use in managing objects, an apparatus for use in managing slots in a page or swap file, and a method for managing a plurality of clustered objects in a container. In still other aspects, the invention includes a computer-readable, program storage medium encoded with instructions that, when performed by a computer, perform such a method and a computer programmed to perform such a method. In one particular embodiment, the invention employs: an allocation bitmap to indicate the state (i.e., in use or free) of various slots in a swap file, a directory bitmap indicating the state of clusters of the slots so that the operating system can quickly locate and allocate slots in the swap file (or files) during a swap, Data structures containing usage counters that indicate how many groups of certain sizes of clusters of free slots can be found in the file, and Lists linking structures for files with compatible usage characteristics.

Claims

1. An apparatus for use in managing objects, the apparatus comprising:

a plurality of containers;

a plurality of clusters populating each container, each cluster comprising a plurality of objects;

a first data structure indicating a state of the objects; and

a second data structure indicating the state of the clusters.

2. The apparatus of claim 1, further comprising a plurality of container control data.

3. The apparatus of claim 1, wherein the container comprises a file.

4. The apparatus of claim 3, wherein the file is a page file or a swap file.

5. The apparatus of claim 3, wherein the objects comprise slots in the file.

6. The apparatus of claim 1, wherein each cluster comprises 16 objects.

7. The apparatus of claim 1, wherein at least one of the first and second data structures comprises a bitmap.

8. The apparatus of claim 1, further comprising at least one usage counter selected from the group consisting of:

a counter of how many free a cluster has;

a counter of how many free clusters are in the container;

a counter of how many sets of 2 adjacent bits are set in the words of the second data structure;

a counter of how many sets of 4 adjacent bits are set in the words of the second data structure;

a counter of how many sets of 8 adjacent bits are set in the words of the second data structure;

a counter of how many sets of 16 adjacent bits are set in the words of the second data structure;

a counter of how many sets of 32 adjacent bits are set in the words of the second data structure; and

a counter of how many sets of 64 adjacent bits are set in the words of the second data structure.

9. The apparatus of claim 8, further comprising at least one data structure containing information indicating that:

the second data structure contains clusters of at least four adjacent free bits;

the second data structure is not empty, but contains no clusters of four adjacent free bits;

the second data structure is empty, but allocation bitmap still shows free pages;

or

the file is full or should not be used.

10. An apparatus, comprising:

a plurality of files;

a plurality of clusters populating each file, each cluster comprising a plurality of slots;

an allocation bitmap indicating a state of the slots; and

a directory bitmap indicating the state of the clusters.

11. The apparatus of claim 10, wherein each file is a page file or a swap file.

12. The apparatus of claim 10, wherein each cluster comprises 16 slots.

13. The apparatus of claim 10, further comprising at least one usage counter selected from the group consisting of:

a counter of how many free slots a cluster has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

14. The apparatus of claim 13, further comprising at least one data structure containing information indicating that:

the directory bitmap contains clusters of at least four adjacent free bits;

the directory bitmap is not empty, but contains no clusters of four adjacent free bits;

the directory bitmap is empty, but the allocation bitmap still shows free pages;

or

the file is full or should not be used.

15. A method for managing a plurality of clustered objects in a container, the method comprising:

tracking a state for each of a plurality of objects populating a container in a first data structure;

tracking a state for cluster of the memory like objects in a second data structure; and

consulting at least one of the first and second data structures to manage the objects.

16. The method of claim 15, further comprising:

constructing the first data structure; and

constructing the second data structure.

17. The method of claim 15, wherein tracking the state for each of the plurality of objects populating the container in the first data structure or tracking the state for cluster of the memory like objects in the second data structure includes tracking in a bitmap.

18. The method of claim 15, further comprising consulting at least one usage counter to manage the objects.

19. The method of claim 18, wherein the consulting the at least one usage counter includes consulting a usage counter selected from the group consisting of:

a counter of how many free pages a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

20. The method of claim 15, further comprising consulting at least one list containing information extracted from usage counters to manage the objects.

21. The method of claim 20, wherein consulting the at least one list includes consulting a list selected from the group consisting of:

a first list containing information indicating whether the second data structure contains clusters of at least four adjacent free bits;

a second list containing information indicating whether the second data structure is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating whether the second data structure is empty, but allocation bitmap still shows free objects;

or

a fourth list containing information indicating that the containers in this list are full or should not be used.

22. A program storage medium encoded with instructions that, when executed by a computing device, perform a method for managing a plurality of clustered objects in a container, the method comprising:

tracking a state for each of a plurality of objects populating a container in a first data structure;

tracking a state for cluster of the objects in a second data structure; and

consulting at least one of the first and second data structures to manage the objects.

23. The program storage medium of claim 22, wherein the encoded method further comprises:

constructing the first data structure; and

constructing the second data structure.

24. The program storage medium of claim 22, wherein tracking the state for each of the plurality of objects populating the container in the first data structure or tracking the state for cluster of the memory like objects in the second data structure in the encoded method includes tracking in a bitmap.

25. The program storage medium of claim 22, wherein the encoded method further comprises consulting at least one usage counter to manage the objects.

26. The program storage medium of claim 25, wherein the consulting the at least one usage counter in the encoded method includes consulting a usage counter selected from the group consisting of:

a counter of how many free pages a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

27. The program storage medium of claim 22, wherein the encoded method further comprises consulting at least one list containing information extracted from usage counters to manage the objects.

28. The program storage medium of claim 27, wherein consulting the at least one list in the encoded method includes consulting a list selected from the group consisting of:

a first list containing information indicating whether the second data structure contains clusters of at least four adjacent free bits;

a second list containing information indicating whether the second data structure is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating whether the second data structure is empty, but the allocation bitmap still shows free objects;

or

a fourth list containing information indicating that the containers in this list are full or should not be used.

29. A computing device programmed to perform a method for managing a plurality of clustered objects in a container, the method comprising:

tracking a state for each of a plurality of objects populating a container in a first data structure;

tracking a state for cluster of the memory like objects in a second data structure; and

consulting at least one of the first and second data structures to manage the objects.

30. The programmed computing device of claim 29, wherein the programmed method further comprises:

constructing the first data structure; and

constructing the second data structure.

31. The programmed computing device of claim 29, wherein tracking the state for each of the plurality of objects populating the container in the first data structure or tracking the state for cluster of the memory like objects in the second data structure in the programmed method includes tracking in a bitmap.

32. The programmed computing device of claim 29, wherein the programmed method further comprises consulting at least one usage counter to manage the objects.

33. The programmed computing device of claim 32, wherein the consulting the at least one usage counter in the programmed method includes consulting a usage counter selected from the group consisting of:

a counter of how many free pages a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

34. The programmed computing device of claim 29, wherein the programmed method further comprises consulting at least one list containing information extracted from usage counters to manage the objects.

35. The programmed computing device of claim 34, wherein consulting the at least one list in the programmed method includes consulting a list selected from the group consisting of:

a first list containing information indicating whether the second data structure contains clusters of at least four adjacent free bits;

a second list containing information indicating whether the second data structure is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating whether the second data structure is empty, but allocation bitmap still shows free objects;

or

a fourth list containing information indicating that the containers in this list are full or should not be used.

36. A method for managing a plurality of clustered slots in a file, the method comprising:

tracking a state for each of a plurality of slots populating a file in a allocation data structure;

tracking a state for cluster of the memory like objects in a directory data structure; and

consulting at least one of the first and directory data structures to manage the slots.

37. The method of claim 36, further comprising:

constructing the allocation data structure; and

constructing the directory data structure.

38. The method of claim 36, wherein tracking the state for each of the plurality of slots populating the file in the allocation data structure or tracking the state for cluster of the memory like objects in the directory data structure includes tracking in a bitmap.

39. The method of claim 36, further comprising consulting at least one usage counter to manage the slots.

40. The method of claim 39, wherein the consulting the at least one usage counter includes consulting a usage counter selected from the group consisting of:

a counter of how many free pages a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

41. The method of claim 36, further comprising consulting at least one list containing information extracted from usage counters to manage the slots.

42. The method of claim 41, wherein consulting the at least one list includes consulting a list selected from the group consisting of:

a first list containing information indicating that the directory data structure for files in this list contains clusters of at least four adjacent free bits;

a second list containing information indicating that the directory data structure for files in this list is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating that the directory data structure for files in this list is empty, but allocation bitmap still shows free slots;

or

a fourth list containing information indicating that files in this list are full or should not be used.

43. A program storage medium encoded with instructions that, when executed by a computing device, perform a method for managing a plurality of clustered slots in a file, the method comprising:

tracking a state for each of a plurality of slots populating a file in a allocation data structure;

tracking a state for cluster of the memory like objects in a directory data structure; and

consulting at least one of the first and directory data structures to manage the slots.

44. The program storage medium of claim 43, wherein the encoded method further comprises:

constructing the allocation data structure; and

constructing the directory data structure.

45. The program storage medium of claim 43, wherein tracking the state for each of the plurality of slots populating the file in the allocation data structure or tracking the state for cluster of the memory like objects in the directory data structure in the encoded method includes tracking in a bitmap.

46. The program storage medium of claim 43, wherein the encoded method further comprises consulting at least one usage counter to manage the slots.

47. The program storage medium of claim 46, wherein the consulting the at least one usage counter in the encoded method includes consulting a usage counter selected from the group consisting of:

a counter of how many free slots a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

48. The program storage medium of claim 43, wherein the encoded method further comprises consulting at least one list containing information extracted from usage counters to manage the slots.

49. The program storage medium of claim 48, wherein consulting the at least one list in the encoded method includes consulting a list selected from the group consisting of:

a first list containing information indicating whether the directory data structure contains clusters of at least four adjacent free bits;

a second list containing information indicating whether the directory data structure is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating whether the directory data structure is empty, but allocation bitmap still shows free slots;

or

a fourth list containing information indicating whether the file is full or should not be used.

50. A computing device programmed to perform a method for managing a plurality of clustered slots in a file, the method comprising:

tracking a state for each of a plurality of slots populating a file in a allocation data structure;

tracking a state for cluster of the memory like objects in a directory data structure; and

consulting at least one of the first and directory data structures to manage the slots.

51. The programmed computing device of claim 50, wherein the programmed method further comprises:

constructing the allocation data structure; and

constructing the directory data structure.

52. The programmed computing device of claim 50, wherein tracking the state for each of the plurality of slots populating the file in the allocation data structure or tracking the state for cluster of the memory like objects in the directory data structure in the programmed method includes tracking in a bitmap.

53. The programmed computing device of claim 50, wherein the programmed method further comprises consulting at least one usage counter to manage the slots.

54. The programmed computing device of claim 53, wherein the consulting the at least one usage counter in the programmed method includes consulting a usage counter selected from the group consisting of:

a counter of how many free slots a file has;

a counter of how many free clusters are in the file;

a counter of how many sets of 2 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 4 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 8 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 16 adjacent bits are set in the words of the directory bitmap;

a counter of how many sets of 32 adjacent bits are set in the words of the directory bitmap; and

a counter of how many sets of 64 adjacent bits are set in the words of the directory bitmap.

55. The programmed computing device of claim 50, wherein the programmed method further comprises consulting at least one list containing information extracted from usage counters to manage the slots.

56. The programmed computing device of claim 55, wherein consulting the at least one list in the programmed method includes consulting a list selected from the group consisting of:

a first list containing information indicating whether the directory data structure contains clusters of at least four adjacent free bits;

a second list containing information indicating whether the directory data structure is not empty, but contains no clusters of four adjacent free bits;

a third list containing information indicating whether the directory data structure is empty, but allocation bitmap still shows free slots;

or

a fourth list containing information indicating whether the file is full or should not be used.