Back to results
US 7,031,971 B1Granted
Lock-free handle resolution
AssigneeMicrosoft Corporation
InventorMartin Taillefer
Life of this patent
Estimating the term…
Abstract
Lock-free resource handle resolution is provided by a handle management system that generates a hierarchy of handle mapping tables such that the number of mapping tables and the number of hierarchical levels can each increase dynamically. Resource handles are generated based on index values associated with pointers stored in the handle mapping tables. Handle resolution can be performed without having to lock the tables because changes to the hierarchical structure of handle mapping tables do not affect handle resolution processing for existing resource handles.
Claims60
A computer implemented method comprising:
- receiving requests for resource handles;
- dynamically generating a hierarchical structure of handle mapping tables such that the number of levels in the hierarchical structure of handle mapping tables dynamically increases as requests for resource handles are received and such that handle mapping tables in a lowest level of the hierarchical structure of handle mapping tables store resource pointers to resources while handle mapping tables in higher levels of the hierarchical structure of handle mapping tables store table pointers to handle mapping tables in lower levels of the hierarchical structure of handle mapping tables;
- and
- generating a resource handle based on index values associated with locations in handle mapping tables at multiple levels of the hierarchical structure of handle mapping tables.
1 more element
A computer implemented method comprising:
- receiving a first request for a resource handle;
- generating a first level-one handle mapping table for storing a predetermined number of indexed resource pointers to resources associated with resource handles;
- storing an indexed resource pointer to a resource associated with the first request in the first level-one handle mapping table;
- receiving a second request for a resource handle that exceeds the predetermined number of indexed resource pointers;
- generating a first level-two handle mapping table for storing table pointers to a predetermined number of level-one handle mapping tables;
- storing a table pointer to the first level-one handle mapping table in a first indexed location associated with the first level-two handle mapping table;
- generating a second level-one handle mapping table for storing the predetermined number of indexed resource pointers;
- storing a table pointer to the second level-one handle mapping table in a second indexed location associated with the first level-two handle mapping table;
- and
- storing an indexed resource pointer to a resource associated with the second request in the second level-one handle mapping table.
7 more elements
A computer implemented method comprising:
- receiving a first request for a resource handle;
- generating a first handle mapping table for storing a predetermined number of indexed resource pointers to resources associated with resource handles;
- storing an indexed resource pointer to a resource associated with the first request in the first handle mapping table;
- receiving a second request for a resource handle;
- and
- in an event that the first handle mapping table is full, generating second and third handle mapping tables wherein the second handle mapping table stores an indexed resource pointer to a resource associated with the second request and wherein the third handle mapping table stores table pointers to the first and second handle mapping tables.
3 more elements
A computer implemented method comprising:
- receiving a request for a resource handle;
- identifying a first handle mapping table at a highest level in a hierarchy of handle mapping tables;
- determining whether the first handle mapping table is full;
- in an event that the first handle mapping table is full, generating a parent handle mapping table;
- storing a table pointer to the first handle mapping table in the parent handle mapping table, such that the parent table represents a new highest level in the hierarchy of handle mapping tables;
- creating a new handle mapping table at each level of the hierarchy below the parent handle mapping table;
- storing a table pointer to each new handle mapping table in a handle mapping table that is one level above the new handle mapping table in the hierarchy;
- and storing a resource pointer to a resource associated with the request in a handle mapping table at a lowest level in the hierarchy of handle mapping tables.
5 more elements
A computer implemented method comprising:
- maintaining a first hierarchical structure of handle mapping tables for storing resource handle information associated with a first system;
- maintaining a second hierarchical structure of handle mapping tables for storing resource handle information associated with a second system;
- associating a first handle set identifier with the first hierarchical structure of handle mapping tables;
- associating a second handle set identifier with the second hierarchical structure of handle mapping tables;
- and
- creating a resource handle associated with the first system based, at least in part, on the first handle set identifier.
3 more elements
A computer implemented method comprising:
- receiving a resource handle;
- identifying one or more index values associated with the resource handle;
- and
- locating a resource pointer associated with the resource handle by using the one or more index values to navigate a hierarchical structure of handle mapping tables without requiring mutually exclusive access to the handle mapping tables.
1 more element
A computer implemented system comprising:
- a processor;
- a memory;
- an operating system;
- a handle management system configured to manage resource handles according to a hierarchical structure of handle mapping tables;
- and a handle creation manager configured to create resource handles by storing resource pointers in indexed locations of handle mapping tables associated with a lowest level of the hierarchical structure of handle mapping tables wherein a handle mapping table associated with a higher level of the hierarchical structure of handle mapping tables stores table pointers to the handle mapping tables associated with the lowest level of the hierarchical structure of handle mapping tables.
2 more elements
A computer implemented system comprising:
- a hierarchical structure of handle mapping tables;
- and
- a handle creation manager configured to:
- create a resource handle by storing a resource pointer to a resource associated with the resource handle in a location of a handle mapping table in the hierarchical structure of handle mapping tables;
- and
- generate the resource handle based on an index associated with the location.
3 more elements
A computer implemented system comprising:
- means for storing a hierarchical structure of handle mapping tables;
- means for dynamically increasing the size of the hierarchical structure of handle mapping tables by adding a parent handle mapping table to existing child handle mapping tables;
- means for storing a resource pointer at an indexed location in a lowest level handle mapping table;
- means for creating a resource handle based on indices associated with indexed locations in one or more of the handle mapping tables;
- and
- means for locating the resource pointer within the hierarchical structure of handle mapping tables without requiring mutually exclusive access to the handle mapping tables.
3 more elements
A computer implemented system comprising:
- means for dynamically generating a hierarchical structure of handle mapping tables such that handle mapping tables at a lowest level of the hierarchical structure of handle mapping tables store resource pointers and handle mapping tables at higher levels of the hierarchical structure of handle mapping tables store pointer to handle mapping tables at a next lower level of the hierarchical structure of handle mapping tables;
- and
- means for generating resource handles based on index values that correspond to locations in handle mapping tables at one or more levels of the hierarchical structure of handle mapping tables.
One or more computer-readable media comprising computer executable instructions that, when executed, direct a computing system to:
- maintain a hierarchical structure of handle mapping tables;
- and
- dynamically increase a number of hierarchical levels associated with the hierarchical structure of handle mapping tables as requests for handles are received such that each higher level handle mapping table references one or more handle mapping tables in a next lower level of the hierarchical structure of handle mapping tables.
One or more computer-readable media comprising computer executable instructions that, when executed, direct a computing system to:
- receive a resource handle;
- extract index values from the resource handle;
- and
- locate a resource associated with the resource handle by traversing a hierarchical structure of handle mapping tables according to the index values such that mutually exclusive access to the tables is not required.
1 more element
One or more computer-readable media comprising a dynamic hierarchical structure for representing resource handles, the structure comprising:
- multiple first level handle mapping tables for storing resource pointers;
- and
- one or more second level handle mapping tables for storing table pointers to the multiple first level handle mapping tables, such that a first level handle mapping table is created when a resource handle is requested and previously created first level handle mapping tables are full.
Dependencies are inferred from the claim text.