Method and system for memory allocation in a multiprocessing environment

• US 6,353,829 B1
• Filed: 12/23/1998
• Issued: 03/05/2002
• Est. Priority Date: 12/23/1998
• Status: Expired due to Term

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Porterfield, Allan, Koblenz, Brian D., Smith, Burton J.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US09/221,657
• Time in Patent Office: 1,168 Days
• Field of Search: 707/100, 712/203, 712/233
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

A method and system for allocating memory. The computer system on which the memory allocation system executes may support the simultaneous execution of multiple threads. Under control of a thread, the memory allocation system first identifies a bin associated with blocks (“lockers”) of memory large enough to satisfy a memory allocation request. When the identified bin has a free locker, the memory allocation system searches a circular list of headers associated with the identified bin for a collection of lockers (“warehouse”) that contains a locker that is available to be allocated. The memory allocation system allocates the found available locker to satisfy the request. If, however, the allocated bin has no free lockers, the memory allocation system allocates a warehouse with lockers large enough to satisfy the memory allocation request. The memory allocation system then adds a warehouse header for the allocated warehouse to a circular list of warehouse headers associated with the identified bin. The memory allocation system allocates a locker from the newly allocated warehouse to satisfy the memory allocation request.

Claims

1. A method in a computer system for removing an item from a circular list that is simultaneously accessible by multiple threads of execution, each item pointing to a next item in the circular list, the method comprising:

during execution of one thread,

identifying an item to be removed from the circular list;

setting the item before the identified item to point to the item after the identified item; and

ensuring that the identified item points to an item of the circular list so that when another thread accesses the identified item after the identified item has been removed from the circular list, the identified item still points to a next item on the circular list.

2. The method of claim 1 wherein the circular list is doubly linked and each item includes a pointer to a previous item, and including:

setting the item after the identified item to point to the item before the identified item.

3. The method of claim 2 wherein the circular list is only traversed in the direction of the next item.

4. The method of claim 1 including setting an indication in the identified item so that when the other thread access the identified item after the identified item has been removed from the circular list, the other thread will proceed to the next item pointed to by the identified item.

5. The method of claim 1 wherein the ensuring that the identified item points to an item of the circular list includes leaving the identified item to point to the item that was the next item before the identified item was removed from the circular list.

6. The method of claim 1 including preventing multiple threads from simultaneously adjusting the number of items in the circular list.

7. The method of claim 1 wherein when another item is removed from the circular list, the other item is set to point to the identified item so that when a thread accesses the other item after the other item has been removed from the circular list, the thread can locate an item still in the circular list through the identified item.

8. The method of claim 1 wherein the circular list and items removed from the circular list form a six list.

9. The method of claim 8 wherein the circular list form a circle portion of the six list and the items removed from the circular list from a tail portion of the circular list.

10. The method of claim 1 wherein the ensuring that the identified item points to an item of the circular list includes setting the identified item to point to another item previously removed from the circular list so that the identified item points to an item of the circular list indirectly through the previously removed item.

11. The method of claim 1 including:

setting a tail pointer to point to the identified item.

12. The method of claim 1 including:

identifying a second item to be removed from the circular list;

setting the item before the second identified item to point to the item after the second identified item; and

setting the second identified item to point to the identified item.

13. The method of claim 12 including:

setting a tail pointer to point to the second identified item.

14. The method of claim 1 wherein the items of the circular list and the items that have been removed form a six list and wherein a removed item is added back to the circular list, by

identifying a removed item;

if the identified removed item does not already point to an item of the circular list, setting the identified removed item to point to an item of the circular list;

setting the item of the circular that is before the item to which the identified removed item points to point to the identified removed item.

15. The method of claim 14 including locking the six list before a removed item is added back to the circular list.

16. The method of claim 14 wherein the identified removed item is the only removed item that points to an item on the circular list.

17. The method of claim wherein items of the circular list are accessible through a circle pointer and items that have been removed are accessible through a tail pointer.

18. A method in a computer system for detecting unauthorized access of a first word of memory, the method comprising:

establishing forwarding for the first word of memory and setting the first word of memory to point to a second word of memory, the second word of memory being a valid memory location; and

establishing forwarding for the second word of memory and setting the second word of memory to point to an invalid memory location

so that when the first word is accessed with forwarding enabled, the access is forwarded to the second word, which is in turn forwarded to the invalid memory location and unauthorized access to the first word is indicated; and

so that when the first word is accessed with forwarding disabled, the pointer to the second word of memory is retrieved and can be used to further access memory.

19. The method of claim 18 wherein the second word of memory is within a data structure that is accessed when the pointer to the second word of memory is retrieved.

20. A computer-readable medium containing a data structure for use in allocating memory, the data structure containing:

a plurality of bins, each bin representing a size of memory that can be allocated from the bin;

for each bin, a circular list of warehouse headers; and

for each warehouse header, a warehouse that contains lockers of the size of memory that can be allocated for the bin.

21. The computer-readable medium of claim 20 wherein a bin contains a pointer to the circular list.

22. The computer-readable medium of claim 20 wherein the circular list is a six list with a circle portion and a tail portion and the bin contains a pointer to the circle portion and a pointer to the tail portion.

23. The computer-readable medium of claim 20 wherein each warehouse header contains a bit vector indicating allocation status of each locker in the warehouse of that warehouse header.

24. The computer-readable medium of claim 23 wherein the bit vector is accessed in a sync synchronization mode.

25. The computer-readable medium of claim 20 wherein each locker of a warehouse contains a pointer to the warehouse header for the warehouse.

26. The computer-readable medium of claim 25 wherein a forward bit of the pointer to the warehouse header is set.

27. The computer-readable medium of claim 26 wherein a forward bit of the word of the warehouse header pointed to by the pointer of a locker is set and the word of the warehouse header pointed to by the pointer of a locker is set to point to an invalid memory location.

28. The computer-readable medium of claim 20 wherein a warehouse header contains a pointer to the warehouse.

29. The computer-readable medium of claim 28 wherein the pointer to the warehouse is accessed in a future synchronization mode.

30. A method in a computer system for allocating memory, the computer system supporting the simultaneous execution of multiple threads, the method comprising:

under control of a thread,

identifying a bin associated with lockers of memory large enough to satisfy a memory allocation request;

when the identified bin has a free locker,

searching a circular list of warehouse headers associated with the identified bin for a warehouse that contains a locker that is available to be allocated; and

allocating the found available locker to satisfy the request;

when the allocated bin has no free lockers

allocating a warehouse with lockers large enough to satisfy the memory allocation request;

adding a warehouse header for the allocated warehouse to a circular list of warehouse headers associated with the identified bin; and

allocating a locker from the allocated warehouse to satisfy the memory allocation request.

31. The method of claim 30 wherein the allocating of a warehouse includes recursively requesting a memory allocation that is large enough to contain multiple lockers for the identified bin.

32. The method of claim 30 wherein when a memory allocation request is for larger than a certain size, using a large memory allocator to allocate the memory.

33. The method of claim 30 wherein access by multiple threads to a warehouse header of the identified bin is coordinated through a synchronization variable with an access mode of sync.

34. The method of claim 33 wherein the synchronization variable is a bit vector with a bit for each locker in the warehouse and each bit indicates whether the locker is allocated.

35. The method of claim 30 wherein the identified bin contains a pointer to the first warehouse header in the circular list and a thread that accesses the circular list changes the pointer to pointer to another warehouse header of the circular list so that a thread that subsequently accesses the circular list will start access at a different warehouse header to minimize attempts at simultaneous access to a warehouse header.

36. The method of claim 30 wherein the identified bin contains a synchronization variable accessed with a future mode to indicate whether the circular list of the bin contains at least one warehouse header.

37. A computer-readable medium containing instructions for controlling a computer system to remove an item from a circular list that is simultaneously accessible by multiple threads of execution, each item pointing to a next item in the circular list, by a method comprising:

identifying an item to be removed from the circular list;

setting the item before the identified item to point to the item after the identified item; and

ensuring that the circular list is accessible through the identified item.

38. The computer-readable medium of claim 37 wherein the circular list is doubly linked and each item includes a pointer to a previous item, and including setting the item after the identified item to point to the item before the identified item.

39. The computer-readable medium of claim 37 wherein the circular list is only traversed in the direction of the next item.

40. The computer-readable medium of claim 37 including setting an indication in the identified item so that when a thread accesses the identified item after the identified item has been removed from the circular list, the thread will proceed to the next item pointed to by the identified item.

41. The computer-readable medium of claim 37 wherein the ensuring that the circular list is accessible through the identified item includes leaving the identified item to point to the item that was the next item before the identified item was removed from the circular list.

42. The computer-readable medium of claim 37 wherein the ensuring that the circular list is accessible through the identified item includes setting the identified item to point to another item previously removed from the circular list so that the identified item points to an item of the circular list indirectly through the previously removed item.

43. The computer-readable medium of claim 37 wherein the items in the circular list and items removed from the circular list form a six list and including preventing multiple threads from simultaneously adjusting the number of items in the six list.

44. The computer-readable medium of claim 37 wherein when another item is removed from the circular list, the other item is set to point to the identified item so that when the other item is accessed after the other item has been removed from the circular list, an item still in the circular list can be located through the identified item.

45. The computer-readable medium of claim 37 wherein the circular list and items removed from the circular list form a six list.

46. The computer-readable medium of claim 45 wherein the items in the circular list form a circle portion of the six list and the items removed from the circular list form a tail portion of the six list.

47. The computer-readable medium of claim 37 including setting a tail pointer to point to the identified item.

48. The computer-readable medium of claim 37 including:

identifying a second item to be removed from the circular list;

setting the item before the second identified item to point to the item after the second identified item; and

setting the second identified item to point to the identified item.

49. The computer-readable medium of claim 48 including:

setting a tail pointer to point to the second identified item.

50. The computer-readable medium of claim 37 wherein the items of the circular list and the items that have been removed from a six list and wherein a removed item is added back to the circular list, by

identifying a removed item;

if the identified removed item does not already point to an item of the circular list, setting the identified removed item to point to an item of the circular list; and

setting the item of the circular that is before the item to which the identified removed item points to point to the identified removed item.

51. The computer-readable medium of claim 50 including locking the six before a removed item is added back to the circular list.

52. A system in a computer system for removing an item from a circular list that is simultaneously accessible by multiple threads of execution, each item pointing to a next item in the circular list, including:

means for identifying an item to be removed from the circular list;

means for setting the item before the identified item to point to the item after the identified item; and

means for ensuring that the circular list is accessible through the identified item.

53. The system of claim 52 wherein the circular list is doubly linked and each item includes a pointer to a previous item, and including means for setting the item after the identified item to point to the item before the identified item.

54. The system of claim 52 wherein the circular list is only traversed in the direction of the next item.

55. The system of claim 52 including means for setting an indication in the identified item so that when a thread accesses the identified item after the identified item has been removed from the circular list, the thread will proceed to the next item pointed to by the identified item.

56. The system of claim 52 wherein the means for ensuring that the circular list is accessible through the identified item leaves the identified item to point to the item that was the next item before the identified item was removed from the circular list.

57. The system of claim 52 wherein the means for ensuring that the circular list is accessible through the identified item sets the identified item to point to another item previously removed from the circular list so that the identified item points to an item of the circular list indirectly through the previously removed item.

58. The system of claim 52 wherein the items in the circular list and items removed from the circular list form a six list and including means for preventing multiple threads from simultaneously adjusting the number of items in the six list.

59. The system of claim 52 wherein when another item is removed from the circular list, means for setting the other item to point to the identified item so that when the other item is accessed after the other item has been removed from the circular list, an item still in the circular list can be located through the identified item.

60. The system of claim 52 wherein the circular list and items removed from the circular list form a six list.

61. The system of claim 60 wherein the items in the circular list form a circle portion of the six list and the items removed from the circular list form a tail portion of the six list.

62. The system of claim 52 including means for setting a tail pointer to point to the identified item.

63. The system of claim 52 including:

means for identifying a second item to be removed from the circular list;

means for setting the item before the second identified item to point to the item after the second identified item; and

means for setting the second identified item to point to the identified item.

64. The system of claim 63 including means for setting a tail pointer to point to the second identified item.

65. The system of claim 52 wherein the items of the circular list and the items that have been removed form a six list and wherein a removed item is added back to the circular list, by

identifying a removed item;

if the identified removed item does not already point to an item of the circular list, setting the identified removed item to point to an item of the circular list; and

setting the item of the circular that is before the item to which the identified removed item points to point to the identifed removed item.

66. The system of claim 65 including means for locking the six list before a removed item is added back to the circular list.

67. The system of claim 65 wherein the identified removed item is the only removed item that points to an item on the circular list.

68. The system of claim 52 wherein items of the circular list are accessible through a circle pointer and items that have been removed are accessible through a tail pointer.