Implementation of memory access control using optimization

• US 20060265557A1
• Filed: 07/28/2006
• Published: 11/23/2006
• Est. Priority Date: 05/02/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: England, Paul, Peinado, Marcus
• Granted Patent: US 7,605,816 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 12/145 the protection being virtual, e.g. for virtual blocks or segments before a translation mechanism
• CPC Class Codes: G06F 21/79 in semiconductor storage media, e.g. directly-addressable memories

Abstract

Mechanisms are disclosed that may allow certain memory access control algorithms to be implemented efficiently. When memory access control is based on controlling changes to an address translation map (or set of maps), it may be necessary to determine whether a particular map change would allow memory to be accessed in an impermissible way. Certain data about the map may be cached in order to allow the determination to be made more efficiently than performing an evaluation of the entire map.

Claims

1. A computer-readable medium encoded with computer-executable instructions to perform a method, the method comprising:

storing information regarding a directed labeled graph that comprises a plurality of vertices and a plurality of labeled edges connecting the vertices, each edge being defined by an ordered pair of the vertices and a label;

performing a first operation that changes said graph by removing or adding a vertex, removing or adding an edge, or changing the label of an edge;

updating said information to reflect the change to said graph; and

determining whether a second operation may be performed based at least in part on said information.

2. The computer-readable medium of claim 1, wherein said graph is representative of an address translation map that comprises a plurality of pages, each page in said address translation map corresponding to a vertex of said graph, each reference within one page of said address translation map to another page of said address translation map corresponding to an edge of said graph, and an attribute associated with a reference corresponding to a label of the reference'"'"'s corresponding edge.

3. The computer-readable medium of claim 1, wherein said graph is stored in a computer memory, and wherein said operation comprises a write to a portion of said computer memory that stores said graph.

4. The computer-readable medium of claim 1, wherein said information comprises data identifying a set of vertices of said graph map that are located at a predetermined distance from a root vertex of said graph.

5. The computer-readable medium of claim 1, wherein said information comprises data identifying a set of vertices of said graph that have a predetermined property.

6. The computer-readable medium of claim 1, wherein said information comprises data indicative of a number of edges leading into a specified vertex.

7. The computer-readable medium of claim 1, wherein said information comprises data indicative of a number of edges that satisfy a specified predicate and that lead into a specified vertex.

8. The computer-readable medium of claim 1, wherein said information comrpises data indicative of a number of edges leading away from a specified vertex in said graph.

9. The computer-readable medium of claim 1, wherein said information comprises data indicative of a number of edges that satisfy a specified predicate and that lead away from a specified vertex.

10. The computer-readable medium of claim 1, wherein whether said second operation may be performed depends upon a given vertex'"'"'s membership in a set, wherein said information contains data indicative of a proper superset of said set, and said act of determining whether said second operation may be performed comprises determining whether said given vertex is a member of said superset.

11. The computer-readable medium of claim 1, wherein whether said second operation may be performed depends upon a given vertex'"'"'s membership in a set, wherein said information contains data indicative of a proper subset of said set, and said act of determining whether said second operation may be performed comprises determining whether said given vertex is a member of said subset.