Reformulating resources with nodes reachable from defined entry points

• US 7,210,124 B2
• Filed: 06/16/2003
• Issued: 04/24/2007
• Est. Priority Date: 06/16/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chan, Hon Keat W.
• Primary Examiner(s): Khatri; Anil
• Application Number:
  US10/463,480
• Publication Number:
  US 20040255273A1
• Time in Patent Office: 1,408 Days
• Field of Search: 717120-123, 717/140, 717162-165, 717168-171, 717/108, 717/116, 717/144
• US Class Current: 717/120
• CPC Class Codes: G06F 9/44521 Dynamic linking or loading; Link editing at or after load time, e.g. Java class loading

Abstract

Historically, resources (e.g., dynamic linked libraries) were organized based on factors including the expertise of development teams. Unfortunately, this creates shared resources of much greater functionality than required by any one client application. By reformulating shared resources according to the nodes reachable from a set of defined entry points, the reformulated resources will contain nodes of relevance. This optimization reduces memory requirements which is useful for embedded systems and for reducing disk accesses.

Claims

1. A method comprising:

receiving a distribution list comprising two or more shared resources comprising dynamically linkable libraries, and two or more classified entry points into the shared resources;

for each classified entry point, identifying a graph of nodes and edges reachable within the shared resources wherein the graph represents basic blocks reachable within the two or more shared resources;

creating a new first order resource comprising a single dynamically linkable file comprising the assembled nodes of a graph representing basic blocks reachable within the two or more shared resources from one or more first order classified entry points;

creating a new second order resource comprising a single dynamically linkable file comprising the assembled nodes of a graph representing basic blocks reachable from one or more second order classified entry points and not reachable from the one or more first order classified entry points;

creating dependency relations for nodes in the new first order resource depended on by nodes in the new second order resource; and

dynamically linking the new first order resource into an application'"'"'s address space in order to provide computing services to a user.

2. The method of claim 1 further comprising:

creating a new third order resource comprising a single dynamically linkable file comprising the assembled nodes of a graph representing basic blocks reachable from one or more third order classified entry points and not reachable from the one or more first or second order classified entry points; and

creating dependency relations for nodes in the new first and second order resources depended on by nodes in the new third order resource.

3. The method of claim 2 wherein a table mapping runtime is injected into the new second and third order resources for resolving dependency relations with explicit links.

4. The method of claim 2 wherein upon executing a third order classified application, the new first, second, and third order resources are loaded into the third order classified application'"'"'s process address space.

5. The method of claim 2 wherein upon executing a second order classified application, the new first and second order resources, but not the new third order resource, are loaded into the second order classified application'"'"'s process address space.

6. The method of claim 2 wherein upon executing a first ordered classified application, the new first order resource, but not the new second or third order resources, are loaded into the first ordered classified application'"'"'s process address space.

7. The method of claim 1 further comprising:

creating plural additional new order resources comprising nodes reachable from entry points classified for each of the new ordered resources; and

creating dependency relations for nodes in the plural new resources that depend on nodes in higher order resources.

8. The method of claim 7 further comprising:

creating a final order resource comprising nodes not-reachable from entry points in the distribution list; and

creating dependency relations for nodes in the final order resource that depend on reachable nodes in the higher order resources.

9. A method of reformulating compiled resources comprising:

receiving a distribution list;

converting resources comprising dynamically linked libraries in the distribution list into an internal representation comprising data structure of information about control flow through basic blocks of the resources comprising dynamically linked libraries;

merging the internal representations into an integrated representation comprising a graph that resolves dependencies between individual resources comprising dynamically linked libraries;

from classified entry points in the distribution list, coloring reachable nodes in the integrated representation with a classification of a color classification of a highest order entry point that reaches a node;

create new resources for each color classification;

inject colored nodes into a new resource of its corresponding color;

inject imports into new resources when nodes of the new resource depend on nodes of a color classification of a higher order;

inject exports into new resources when nodes of the new resource are depended on by nodes of a color classification of a lower order; and

dynamically linking at least one new resource into an application'"'"'s address space in order to provide computing services to a user.

10. The method of claim 9 further comprising:

injecting a table mapping runtime into new resources with imports.

11. The method of claim 9 wherein coloring nodes reachable in the integrated representation comprises pushing descendant nodes into a pending list.

12. The system of claim 11 wherein nodes are basic blocks, and already colored basic blocks taken from the pending list are marked for requiring import and export relations.

13. The method of claim 9 wherein the created new resources have a one-way dependency relationship wherein no higher order color classification new resource depends on any lower order color classification new resource.

14. A computer system comprising:

a CPU coupled to main memory and secondary memory;

the memory comprising a node identifier for walking a control flow through reachable basic blocks to create graphs of basic blocks reachable in plural shared resources comprising dynamic linkable files, a resource reformulator for assembling reachable basic blocks in created graphs into a shared resource comprising a dynamically linkable file, a dependency redirector, plural shared resources, and a distribution list comprising a list of classified entry points, each entry point associated with a new shared resource name, and each entry point represents a graph of reachable nodes in the shared resources; and

the memory further comprising an application providing requested computing services to a user, wherein the application is dynamically linked to a shared resource comprising a dynamically linkable file including basic blocks assembled from plural shared resources.

15. The system of claim 14 wherein the distribution list further comprises a request to reformulate the new shared resources with the graphs of reachable nodes.

16. The method of claim 14 wherein the distribution list further comprises a request to the dependency redirector, to create one way dependency relations for the new shared resources.

17. A computer-readable storage medium having executable instructions for performing a method comprising:

receiving a distribution list comprising two or more shared resources, and two or more classified entry points into the shared resources;

for each classified entry point, identifying a graph of nodes and edges reachable within the shared resources, each shared resources comprising a dynamically linkable file with the nodes comprising basic blocks reachable via control flow through the edges of the graph;

creating a new first order resource comprising a dynamically linkable file of assembled nodes reachable from first order classified entry points;

creating a new second order resource comprising a dynamically likable file of assembled nodes reachable from second order classified entry points and not reachable from first order classified entry points; and

creating dependency relations for nodes in the first order resource depended on by nodes in the second order resource.

18. The computer-readable storage medium of claim 17 further comprising:

creating a new third order resource comprising a dynamically linkable file of assembled nodes reachable from third order classified entry points and not reachable from first or second order classified entry points; and

creating dependency relations for nodes in the first and second order resources depended on by nodes in the third order resource.

19. The computer-readable storage medium of claim 18 further comprising:

a table mapping runtime is injected into the new second and third order resources for resolving dependency relations with explicit links.

20. A computer-readable storage medium of claim 18 further comprising:

upon executing a third order classified application, the new first, second, and third order resources are loaded into the third order classified applications process address space.

21. A computer-readable storage medium of claim 18 further comprising:

upon executing a second order classified application, the new first and second order resources, but not the new third order resource, are loaded into the second order classified application'"'"'s process address space.

22. A computer-readable storage medium of claim 18 further comprising:

upon executing a first ordered classified application, the new first order resource, but not the new second or third order resource, are loaded into the first ordered classified application'"'"'s process address space.

23. A computer-readable storage medium of claim 17 further comprising:

creating plural additional new order resources comprising a dynamically linkable file of assembled nodes reachable from entry points classified for each of the new ordered resources; and

creating dependency relations for nodes in the plural new resources that depend on nodes in higher order resources.

24. A computer-readable storage medium of claim 23 further comprising:

creating a final order resource comprising a dynamically linkable file of assembled nodes not-reachable from entry points in the distribution list; and

creating dependency relations for nodes in the final order resource that depend on reachable nodes in the higher order resources.

25. A method of reformulating compiled resources comprising:

displaying a list of application programming interfaces available for accessing shared resources;

receiving selections of application programming interfaces;

converting selections into a distribution list;

creating an internal representation of nodes reachable from entry points in the distribution list, the internal representation comprising data about control flow through basic blocks of the resources comprising plural dynamically linkable libraries; and

creating a new resource comprising the internal representation and executing the new resource locally in a process address space of an executing application program providing computing services to a user.

26. A method of reformulating compiled resources comprising:

displaying a list of application programming interfaces available for accessing shared resources;

receiving selections of application programming interfaces, wherein selections include classifications;

converting selections and classifications into a distribution list;

creating an internal representation of nodes reachable from entry points in the distribution list;

coloring reachable nodes in the integrated representation with a color classification of a highest order classified entry point that reaches a node;

creating a new resources for each color classification;

injecting colored nodes into a new resource of its corresponding color;

injecting imports into new resources when nodes of the new resource depend on nodes of a color classification of a higher order;

injecting exports into new resources when nodes of the new resource are depended on by nodes of a color classification of a lower order; and

dynamically linking the created new resources for at least two or more color classifications into the address space for a single application providing local computing services to a user.