Caching permissions information

• US 7,340,463 B1
• Filed: 06/25/2004
• Issued: 03/04/2008
• Est. Priority Date: 06/25/2004
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: O'Rourke, David M., Vaughan, Greg B.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): VY, HUNG T
• Application Number:
  US10/877,048
• Time in Patent Office: 1,348 Days
• Field of Search: 709/223, 709/220, 709/201, 707/3, 707/2, 707/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A method for determining group membership in a computer system, the method comprising: obtaining an identifier that describes a member of a group, the member of a group having a member hash table that contains group membership information describing to what groups a member belongs; performing a primary search of a plurality of groups to determine if each group contains the member'"'"'s identifier, each group in the plurality having a group hash table that describes to what other groups the group belongs, caching the results of the primary search in the member hash table, for each group to which the member belongs, performing a secondary search of a plurality of groups to determine what groups contain the group to which the member belongs, and caching the results of the secondary search into the group hash table and merging the results into the member hash table, and reading the member hash table to determine group membership.

Claims

1. A method for determining group membership in a computer system, the method comprising:

obtaining an identifier that describes a member of a group, the member of a group having a member hash table that contains group membership information describing to what groups a member belongs;

performing a primary search of a first plurality of groups to determine if each group contains the identifier, each group in the first plurality having a group hash table that describes to what other groups the group belongs;

caching the results of the primary search in the member hash table;

for each group to which the member belongs;

performing a secondary search of a second plurality of groups to determine what groups contain the group to which the member belongs; and

caching the results of the secondary search into the group hash table and merging the results into the member hash table; and

reading the member hash table to determine group membership.

2. The method of claim 1, wherein the secondary search is performed recursively on all subgroups within the second plurality of groups and the results are cached in the group hash table and merged into the member hash table.

3. The method of claim 1, wherein the member hash table expires when the group hash table expires.

4. The method of claim 1, wherein said method is adapted for use in a computer system comprising an access control list, wherein the access control list comprises a set of access rights for each group in the first plurality of groups.

5. The method of claim 4, wherein each set of access rights comprises rules for directory and service access.

6. The method of claim 4, wherein said identifier uniquely corresponds to a user of the computer system.

7. The method of claim 1, further comprising constructing an inverse mapping of group information stored within the member hash table.

8. The method of claim 1, wherein said performing a secondary search of a second plurality of groups to determine what groups contain the group to which the member belongs comprises utilizing a recursive procedure.

9. The method of claim 1, further comprising updating the member hash table when group information changes.

10. A computer-readable medium containing instructions which, when executed by a computer, determine group membership in a computer system, by:

obtaining an identifier that describes a member of a group, the member of a group having a member hash table that contains group membership information describing to what groups a member belongs;

performing a primary search of a first plurality of groups to determine if each group contains the identifier, each group in the first plurality having a group hash table that describes to what other groups the group belongs;

caching the results of the primary search in the member hash table;

for each group to which the member belongs;

performing a secondary search of a second plurality of groups to determine what groups contain the group to which the member belongs; and

caching the results of the secondary search into the group hash table and merging the results into the member hash table; and

reading the member hash table to determine group membership.

11. The computer-readable medium of claim 10, wherein said computer-readable medium is adapted for use in a computer system comprising an access control list, wherein the access control list comprises a set of access rights for each group in the first plurality of groups.

12. The computer-readable medium of claim 11, wherein each set of access rights comprises rules for directory and service access.

13. The computer-readable medium of claim 11, wherein said identifier uniquely corresponds to a user of the computer system.

14. The computer-readable medium of claim 10, further comprising instructions which, when executed by a computer, construct an inverse mapping of group information stored within the member hash table.

15. The computer-readable medium of claim 10, wherein said performing a secondary search of a second plurality of groups to determine what groups contain the group to which the member belongs comprises utilizing a recursive procedure.

16. The computer-readable medium of claim 10, further comprising instructions which, when executed by a computer, update the member hash table when group information changes.

17. A device comprising:

means for obtaining an identifier that describes a member of a group, the member of a group having a member hash table that contains group membership information describing to what groups a member belongs;

means for performing a primary search of a first plurality of groups to determine if each group contains the identifier, each group in the first plurality having a group hash table that describes to what other groups the group belongs;

means for caching the results of the primary search in the member hash table;

for each group to which the member belongs;

means for performing a secondary search of a second plurality of groups to determine what groups contain the group to which the member belongs; and

means for caching the results of the secondary search into the group hash table and merging the results into the member hash table; and

means for reading the member hash table to determine group membership.

18. The device of claim 17, further comprising means for updating the member hash table when group information changes.

19. The device of claim 17, further comprising means for building a list of users with membership attributes which need to be updated.

20. The device of claim 17, further comprising means for constructing an inverse mapping of group information stored within the member hash table.

21. A method for determining group membership in a computerized device, the method comprising:

providing an identifier of a member of a group, the member having first information describing to what groups said member belongs associated therewith;

performing a search of a first plurality of groups to determine which of said groups contain the identifier, each group in the first plurality having second information that describes to what other groups that group belongs;

storing the results of the search with said first information;

for each group to which the member belongs;

performing a search of a second plurality of groups to determine what groups include the group to which the member belongs; and

storing the results of said search of a second plurality with said second information, and merging both said results and second information into the first information to produce merged information; and

accessing the merged information to determine group membership.

22. The method of claim 21, wherein said method is adapted for use in a computerized device comprising an access control list, wherein the access control list comprises a set of access rights for each group in the first plurality of groups.

23. The method of claim 22, wherein each set of access rights comprises rules for directory and service access.

24. The method of claim 21, wherein said identifier uniquely corresponds to a user of the computerized device.

25. The method of claim 21, further comprising constructing an inverse mapping of group information stored with the first information.

26. The method of claim 21, wherein said performing a search of a second plurality of groups comprises utilizing a recursive procedure.

27. The method of claim 21, further comprising updating the first information when group information changes.

28. A computer-readable medium containing instructions which, when executed by a computer, determine group membership in a computer system, by:

obtaining an identifier of a member of a group, the member having first information describing to what groups said member belongs associated therewith;

performing a search of a first plurality of groups to determine which of said groups contain the identifier, each group in the first plurality having second information that describes to what other groups that group belongs;

storing the results of the search with said first information;

for each group to which the member belongs;

performing a search of a second plurality of groups to determine what groups include the group to which the member belongs; and

storing the results of said search of a second plurality with said second information, and merging both said results and second information into the first information to produce merged information; and

accessing the merged information to determine group membership.

29. A method for determining group membership in a computer system, comprising:

providing an identifier of a member of a group, at least one of the member or identifier having first information describing to what groups said member belongs associated therewith;

performing a search of a first plurality of groups to determine which of said groups contain the identifier, each group in the first plurality having second information that describes to what other groups that group belongs;

storing the results of the search with said first information;

for each group to which the member belongs;

performing a search of a second plurality of groups to determine what groups include the group to which the member belongs; and

combining (i) the results of said search of a second plurality, (ii) said second information, and (iii) said first information, so as to produce merged information; and

accessing the merged information to determine group membership.

30. The method of claim 29, wherein said method is adapted for use in a computer system comprising an access control list, wherein the access control list comprises a set of access rights for each group in the first plurality of groups.

31. The method of claim 30, wherein each set of access rights comprises rules for directory and service access.

32. The method of claim 29, wherein said identifier uniquely corresponds to a user of the computer system.

33. The method of claim 29, further comprising constructing an inverse mapping of group information stored with the first information.

34. The method of claim 29, wherein said performing a search of a second plurality of groups comprises utilizing a recursive procedure.

35. The method of claim 29, further comprising updating the first information when group information changes.