Generation, validation and reservation of reference handles

• US 6,636,874 B1
• Filed: 06/29/2000
• Issued: 10/21/2003
• Est. Priority Date: 06/23/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Bernet, Yoram
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/608,351
• Time in Patent Office: 1,209 Days
• Field of Search: 707/9, 707/2, 707/201, 707/100, 709/225, 709/229, 711/150, 711/151, 711/152
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4493 Object persistence
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

The present described embodiments are embodied in a system and method for generating and validating reference handles for consumers requiring access to resources in a computer system. The system of the present described embodiments includes a resource manager having a handle administrator, a plurality of consumers, and a plurality of resources. The handle administrator includes an assignment routine, a release routine, and a dereference routine. The assignment routine issues new handles, the release routine releases handles that are no longer required (thus rendering the handle invalid), and the dereference routine dereferences handles into a pointer to a resource, which entails verifying that the handle is valid. Also included is an auxiliary sub-routine for managing used and unused records, an expansion sub-routine for efficiently expanding the handle database, a handle recycling sub-routine for recycling handles, a contraction sub-routine for efficiently contracting the handle database, a hysteresis sub-routine for probabilistically contracting the handle database, and a memory allocation failure sub-routine to improve functionality in the event of memory allocation failure. Further, the systems and methods include routines that enable a handle value to be reserved for an indication of a lack of a valid handle. The reserved handle value is never issued to a consumer for use in accessing a resource.

Claims

1. A computer-implemented method for managing data access to at least one resource of a computer system, said method comprising:

allocating an area in computer readable memory for an original handle database containing at least one reference handle;

reserving a handle value that is never to be issued, the reserved handle value being reserved for an indication of a lack of a valid handle;

issuing a new handle that does not correspond to the reserved handle value to a consumer when said consumer requires access to at least one of the resources;

associating said issued handle with said resource requiring access by assigning a unique value to said issued handle;

verifying that said issued handle is valid;

dereferencing said verified handle in constant time into a pointer to said resource requiring access;

releasing issued handles and deeming their respective handle values as being unassigned for handles that are no longer required by consumers and classifying said released handles as invalid; and

wherein said method generates and validates handles for providing efficient management and administration of consumers'"'"' access to resources in computer systems.

2. The method of claim 1, further comprising managing assigned and unassigned handle values with a set of records, each record containing fields, one field of each record being a handle value field indicating a handle value.

3. The method of claim 2, wherein said managing assigned and unassigned handle values comprises:

maintaining a list of records, wherein the handle value fields of said records indicate unassigned handle values;

selecting a handle value from said list with indicia of unassigned handle values when a new handle is to be issued; and

adding a released handle value to said list with indicia of unassigned handles when a handle is released.

4. The method of claim 3, wherein said maintained list is a linked list, wherein issued handles are assigned previously unassigned handle values from records at a head portion of said list and wherein released handles values are placed in records at a tail portion of said list.

5. The method of claim 3, wherein said maintained list is a search tree and wherein an unassigned handle value with the lowest handle value among all unassigned handle values is selected first to be assigned to an issued handle.

6. The method of claim 1, further comprising dynamically expanding said original handle database in response to predefined conditions.

7. The method of claim 6, wherein said dynamically expanding the original handle database comprises:

allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

copying data located in said original handle database into said expanded handle database;

conditionally recomputing data copied into said expanded handle database;

reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

8. The method of claim 7, wherein said multiplicative constant is two.

9. The method of claim 1, furthering comprising recycling handle values.

10. The method of claim 1, further comprising dynamically contracting said original handle database by:

allocating an area in said computer readable memory for a contracted handle database half the size of said original handle database size;

copying data located in said original handle database into said contracted handle database;

conditionally recomputing data copied into said contracted handle database;

reorganizing said copied data in said contracted handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

11. The method of claim 10, further comprising dynamically expanding the original handle database by:

allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

copying data located in said original handle database into said expanded handle database;

conditionally recomputing data copied into said expanded handle database;

reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

12. The method of claim 11, further comprising probabilistically contracting said handle database by:

maintaining a computational debt value;

initially setting said computational debt value to zero;

increasing said computational debt value by a predetermined expansion value each time said handle database is expanded;

increasing said computational debt value by a predetermined contraction value each time said handle database is contracted;

decreasing said computational debt value by a predetermined issue value each time a handle is issued;

decreasing said computational debt value by a predetermined release value each time a handle is release; and

contracting said handle database only if said computational debt is equal to zero.

13. The method of claim 6, further comprising revoking at least one handle when said handle database cannot be dynamically expanded.

14. The method of claim 13, wherein said revoking at least one handle comprises:

placing an issued handle in a record at a tail portion of an assigned list each time it is issued;

removing a record from said assigned list when said handle indicated by a field in said record is released; and

revoking a handle in response to predefined conditions and removing a record containing a field that indicates the handle being revoked from a head portion of said assigned list.

15. The method of claim 1, further comprising:

preventing simultaneous issuing of new handles with a multithread lock; and

preventing simultaneous releasing of issued handles with said multithread lock.

16. A management device for managing data access to a plurality of resources stored on computer readable memory of a computer system, said management device comprising:

an original handle database stored in the computer readable memory of the computer system and containing a plurality of reference handles;

a handle value that is reserved and is never to be issued, the reserved handle value being reserved for an indication of a lack of a valid handle;

a plurality of consumers randomly requiring access to said resources; and

a handle administrator comprising,

an assignment module for issuing a new handle that does not correspond to the reserved handle value from said original handle database to a requesting consumer when said requesting consumer requires access to a specified resource and for associating said issued handle with said specified resource by assigning a unique value to said issued handle,

a dereference module for verifying that said issued handle is valid and for dereferencing said issued handle in constant time into a pointer to said specified resource, and

a release module for releasing issued handles and deeming their respective handle values as being unassigned for handles that are no longer required by consumers and classifying said released handles as invalid.

17. The management device of claim 16, wherein said assignment module further comprises an auxiliary sub-module for managing assigned and unassigned handle values with a set of records, each record containing fields, one field of each record being a handle value field indicating a handle value.

18. The management device of claim 17, wherein said auxiliary sub-module comprises:

a list of records, wherein the handle value fields of said records indicate unassigned handle values;

a device for selecting a handle value from said list with indicia of unassigned handle values when a new handle is to be issued; and

a device for adding a released handle value to said list with indicia of unassigned handle values when a handle is released.

19. The management device of claim 18, wherein said list is a linked list and wherein handle values are selected from records at a head portion of said list when issued and are placed in records at a tail portion of said list when released.

20. The management device of claim 18, wherein said list is a search tree and wherein handle values with the lowest handle value among unassigned handle values are selected first when issued.

21. The management device of claim 16, further comprising an expansion sub-module for dynamically expanding said handle database in response to predefined conditions.

22. The management device of claim 21, wherein said expansion sub-module comprises:

a allocate routine for allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

a copy routine for copying data located in said original handle database into said expanded handle database;

a conditional recomputation routine for conditionally recomputing data copied into said expanded handle database;

a reorganize routine for reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

a deallocate routine for deallocating said area in said computer readable memory occupied by said original handle database.

23. The management device of claim 22, wherein said multiplicative constant is two.

24. The management device of claim 16, further comprising a recycle handle values sub-module adapted for efficiently recycling handle values.

25. The management device of claim 24, wherein said recycle handle values sub-module is user activateable.

26. The management device of claim 16, further comprising a contraction module for dynamically contracting said original handle database in response to predefined conditions by:

an allocate routine for allocating an area in said computer readable memory for a contracted handle database half the size of said original handle database size;

a copy routine for copying data located in said original handle database into said contracted handle database;

a conditional recomputation routine for conditionally recomputing data copied into said contracted handle database;

a reorganize routine for reorganizing said copied data in said contracted handle database so as to prevent a future conflict in handle values; and

a deallocate routine for deallocating said area in said computer readable memory occupied by said original handle database.

27. The management device of claim 26, wherein said assignment module further comprises an expansion sub-module for dymanically expanding said original handle database, said expansion module comprising:

an allocate routine for allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

a copy routine for copying data located in said original handle database into said expanded handle database;

a conditional recomputation routine for conditionally recomputing data copied into said expanded handle database;

a reorganize routine for reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

a deallocate routine for deallocating said area in said computer readable memory occupied by said original handle database.

28. The management device of claim 27, further comprising a hysteresis sub-module for probabilistically contracting said handle database, said hysteresis sub-module comprising:

a maintain routine for maintaining a computational debt value;

a set routine for initially setting said computational debt value to zero;

a first increase routine for increasing said computational debt value by a predetermined expansion value each time said handle database is expanded;

a second increase routine for increasing said computational debt value by a predetermined contraction value each time said handle database is contracted;

a first decrease routine for decreasing said computational debt value by a predetermined issue value each time a handle is issued;

a second decrease routine for decreasing said computational debt value by a predetermined release value each time a handle is release; and

a contract routine for contracting said handle database only if said computational debt is equal to zero.

29. The management device of claim 16, wherein said assignment module further includes a memory allocation failure sub-module for revoking at least one handle when said handle database cannot be expanded.

30. The management device of claim 29, wherein said memory allocation failure sub-module comprises:

a placement routine for placing an issued handle in a record at a tail portion of an assigned list each time it is issued;

a remove routine for removing a record from said assigned list when said handle indicated by a field in said record is released; and

a revoke routine for revoking a handle in response to predefined conditions and removing a record containing a field that indicates the handle being revoked from a head portion of said assigned list.

31. A computer readable medium having computer-executable components for causing a computer to function as a resource administration system for generating and validating reference handles for consumers requiring access to a plurality of resources, said system comprising:

a computer-readable storage medium; and

a computer data access system stored on said medium, said computer data access system having a handle administrator and an original handle database stored in said computer-readable storage medium, said original handle database containing a plurality of reference handles and having a handle value that is reserved and is never to be issued, the reserved handle value being reserved for an indication of a lack of a valid handle;

wherein said computer data access system is preprogrammed for,

issuing a new handle having a handle value that is not the reserved handle value from said original handle database to a requesting consumer when said requesting consumer requires access to a specified resource and for associating said issued handle with said specified resource by assigning a unique value to said issued handle,

verifying that said issued handle is valid and for dereferencing said issued handle in constant time into a pointer to said specified resource, and

releasing issued handles and deeming their respective handle values as being unassigned for handles that are no longer required by consumers and classifying said released handles as invalid.

32. The resource administration system of claim 31, wherein said computer data access system is further preprogrammed for managing assigned and unassigned handle values with a set of records, each record containing fields, one field of each record being a handle value field indicating a handle value.

33. The resource administration system of claim 32, wherein said computer data access system manages assigned and unassigned handle values of said original handle database by:

maintaining a list of records, wherein the handle value fields of said records indicate unassigned handle values;

selecting a handle value from said list with indicia of unassigned handle values when a new handle is to be issued; and

adding a released handle value to said list with indicia of unassigned handle values when a handle is released.

34. The resource administration system of claim 33, wherein said list is a linked list and wherein handle values are selected from records at a head portion of said list when issued and are placed in records at a tail portion of said list when released.

35. The resource administration system of claim 33, wherein said list is a search tree and wherein handle values with the lowest handle value among unassigned handle values are selected first when issued.

36. The resource administration system of claim 31, wherein said computer data access system is further preprogrammed for dynamically expanding said handle database in response to predefined conditions.

37. The resource administration system of claim 36, wherein said computer data access system dynamically expands said handle database by:

allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

copying data located in said original handle database into said expanded handle database;

conditionally recomputing data copied into said expanded handle database;

reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

38. The resource administration system of claim 37, wherein said multiplicative constant is two.

39. The resource administration system of claim 31, wherein said computer data access system is further preprogrammed for recycling handle values.

40. The resource administration system of claim 39, wherein said recycling of handle values is user activateable.

41. The resource administration system of claim 31 further comprising a contraction module for dynamically contracting the original handle database in response to predefined conditions by:

allocating an area in said computer readable memory for a contracted handle database half the size of said original handle database size;

copying data located in said original handle database into said contracted handle database;

conditionally recomputing data copied into said contracted handle database;

reorganizing said copied data in said contracted handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

42. The resource administration system of claim 41, wherein said computer data access system is further preprogrammed for dynamically expanding said original handle database by:

allocating an area in said computer readable memory for an expanded handle database having a size of a multiplicative constant larger than said original handle database size;

copying data located in said original handle database into said expanded handle database;

conditionally recomputing data copied into said expanded handle database;

reorganizing said copied data in said expanded handle database so as to prevent a future conflict in handle values; and

deallocating said area in said computer readable memory occupied by said original handle database.

43. The resource administration system of claim 42, wherein said computer data access system is further preprogrammed for probabilistically contracting said handle database by:

maintaining a computational debt value;

initially setting said computational debt value to zero;

increasing said computational debt value by a predetermined expansion value each time said handle database is expanded;

increasing said computational debt value by a predetermined contraction value each time said handle database is contracted;

decreasing said computational debt value by a predetermined issue value each time a handle is issued;

decreasing said computational debt value by a predetermined release value each time a handle is release; and

contracting said handle database only if said computational debt is equal to zero.

44. The resource administration system of claim 31, wherein said computer data access system is further preprogrammed for revoking at least one handle when said handle database cannot be expanded.

45. The resource administration system of claim 44, wherein said computer data access system revokes at least one handle by:

placing an issued handle in a record at a tail portion of an assigned list each time it is issued;

removing a record from said assigned list when said handle indicated by a field in said record is released; and

revoking a handle in response to predefined conditions and removing a record containing a field that indicates the handle being revoked from a head portion of said assigned list.