Virtual memory management and allocation arrangement for digital data processing system

Claim 3

The system of claim 1 wherein said array data to be stored has a characteristic one of said predetermined dimensions, and said allocator uses said table to identify segments that have been allocated to store array data having said characteristic dimension.

Claim 4

The system of claim 2 wherein said allocator uses said table to identify segments that have not been allocated to store array data if no said segments have been allocated to store array data having said characteristic dimension.

Claim 5

The system of claim 3 further comprising a map that identifies, for each said segment, which portions of said segment have been allocated to store array data, and wherein said allocator uses one or more of said identified segments with said map to identify said contiguous portion of said virtual address space.

Claim 6

The system of claim 1 wherein said table comprises lists of records for segments that have bene at least partially allocated to store array data, each list being associated with a different predetermined dimension, and each record in each list being associated with a segment with has been at least partially allocated to store array data having the different predetermined dimension associated with said list.

Claim 7

The system of claim 5 wherein said table further comprises a list of records for segments that have not been allocated to store any array data.

Claim 8

The system of claim 5 wherein, a list includes at least one record identifying another record, thereby comprising a linked list of records.

Claim 9

The system of claim 5 wherein each record in said table identifies the different predetermined dimension of the array data that an associated segment has been allocated to store.

Claim 10

The system of claim 5 wherein each record in said table identifies whether portions of an associated segment have not been allocated to store array data.

Claim 11

The system of claim 9 wherein each record in said table identifies whether an associated segment has not been allocated to store array data.

Claim 12

The system of claim 9 wherein each record in said table identifies whether an associated segment has been completely allocated to store array data.

Claim 13

The system of claim 5 further comprising a map that identifies portions of a segment which have been allocated to store array data, and said allocator uses said map to identify a contiguous portion of said virtual address space.

Claim 14

The system of claim 12 wherein said allocator uses said lists of records to identify segments that have been at least partially allocated to store array data having a characteristic one of said predetermined dimensions, and uses said identified segments with said map to identify a contiguous portion of virtual address space.

Claim 15

The system of claim 13 wherein said allocator uses said list of records to identify segments that have not been allocated to store array data to identify said contiguous portion of said virtual address space.

Claim 16

The system of claim 14 wherein, if said table does not include a list of records for segments that have been at least partially allocated to store array data having said characteristic dimension, said allocator uses said list of records for unallocated segments to identify one or more segments, and uses said one or more identified segments with said map to identify said contiguous portion of said virtual address space.

Claim 17

The system of claim 14 wherein, if said contiguous portion of said virtual address space includes an unallocated segment, said allocator moves the record associated with said segment from the list of records associated with unallocated segments to a list associated with said characteristic dimension.

Claim 18

The system of claim 16 wherein, if said table did not include a list for said characteristic dimension, said allocator causes said lists to be created by designating said record as the first record in said list.

Claim 19

The system of claim 5 further comprising a map that identifies, for each said segment, which portions of said segment have been allocated to store array data, and wherein said allocator includes a deallocator for freeing a contiguous portion of said virtual address space using said table and said map when array data stored in said contiguous portion is to be removed from said memory.

Claim 20

The system of claim 18 wherein a record contains information about a segment that was allocated to store said array data to be removed, said deallocator causing said record to be updated when said contiguous portion of said virtual address space is freed.

Claim 21

The system of claim 19 wherein said information identifies whether said segment is completely allocated or is completely unallocated.

Claim 22

The system of claim 20 wherein said deallocator causes said record to be moved to the list of records for segments that have not been allocated to store any array data if said segment becomes completely unallocated when said contiguous portion of said virtual address space is freed.

Claim 23

The system of claim 1 wherein said segments comprise contiguous blocks for storing array data, said system further comprising a map that identifies which portions of said segments have been allocated to store array data, and wherein each said segment comprises a number of contiguous blocks for storing said array data, said map being arranged to identify which ones of said contiguous blocks have bene allocated to store array data.

Claim 24

The system of claim 22 wherein said map comprises an entry associated with each said segment and a plurality of elements associated with each said segment, each element indicating whether a block of an associated element has been allocated to store array data.

Claim 25

The system of claim 23 wherein said array data to be stored has a characteristic one of said predetermined dimensions said allocator testing said map based on said characteristic dimension to identify one or more contiguous elements in said map associated with one or more contiguous blocks.

Claim 26

The system of claim 24 wherein said allocator uses said table to identify one or more entries of said map that are associated with segments that have at least partially been allocated to store array data having said characteristic dimension, and to test the elements or said identified entries to identify said one or more contiguous elements associated with said one or more contiguous blocks.

Claim 27

The system of claim 25 wherein, if no said segments have been allocated to store array data having said characteristic dimension, said allocator uses said table to identify one or more entries that are associated with segments that have not been allocated to store array data, and tests the elements of said identified entries to identify said one or more contiguous elements associated with said one or more contiguous blocks.

Claim 28

The system of claim 25 wherein said allocator ignores, during said testing of elements of said identified entries in the map that are associated with segments that have been at least partially allocated to store array data having a dimension different from said characteristic dimension.

Claim 29

The system of claim 27 wherein said allocator tests said identified entries by counting the number of contiguous elements associated with blocks that have not been allocated to store array data and compare the number counted with the number of blocks in said characteristic dimension.

Claim 30

The system of claim 28 wherein said allocator starts said counting in the first entry identified by said table that is associated with a segment that has been at least partially allocated to store array data having said characteristic dimension.

Claim 31

The system of claim 29 wherein said allocator starts said counting at the first element in said first entry that is associated with an unallocated block in said segment.

Claim 32

The system of claim 29 wherein, if no said segments have been allocated to store array data having said characteristic dimension, said allocator starts said counting at the first element in the first entry identified by said table that is associated with a segment that has not been allocated to store array data.

Claim 33

The system of claim 30 wherein, if said allocator has reached a count that is less than the number of blocks in said characteristic dimension when said allocator has tested all elements in said first entry, said allocator continues counting elements in the entry associated with a next contiguous segment if said next segment is either unallocated or has been partially allocated to store array data having said characteristic dimension.

Claim 34

The system of claim 32 wherein said allocator restarts said counting if it finds an element associated with an allocated block.

Claim 35

The system of claim 24 wherein said allocator includes a deallocator for freeing a contiguous portion of said virtual address space using said table and said map when array data stored in said contiguous portion is to be removed from said memory.

Claim 36

The system of claim 34 wherein said deallocator uses said table to identify at least one segment that contains at least some of said virtual address space to be freed, and to access the entry of said map that is associated with said segment to identify contiguous elements of one or more entries in said map that are associated with the blocks that comprise the contiguous portion of said virtual address space to be freed.

Claim 37

The system of claim 35 wherein said deallocator causes each one of said contiguous elements to indicate that its associated block has not been allocated to store array data when said contiguous portion of said virtual address space has been freed.

Claim 38

The system of claim 1 further comprising a map that identifies, for each said segment, which portions of said segment have been allocated to store array data, and wherein said array data to be stored has a characteristic one of said predetermined dimensions, said segments being contiguous within said virtual address space and each said segment comprising a predetermined number of contiguous blocks for storing array data, said table comprising lists of records for segments that have been at least partially allocated to store array data, each list being associated with a different predetermined dimension, and each record in each list being associated with a segment which has been at least partially allocated to store array data and identifying another record in said list, said table further including a list of records for segments that have not been allocated to store array data, said map comprising an entry associated with each said segment and a plurality of elements in each entry associated with the contiguous blocks in the corresponding segment, each element indicating whether its associated block has been allocated to store array data, and wherein said space allocator uses said lists of records to identify segments that have been at least partially allocated to store array data having said characteristic dimension or that have not been allocated to store array data to identify one or more candidate segments for storing said array data, said space allocator further testing the elements of bit map entries that correspond to said candidate segments to identify one or more contiguous elements associated with one or more contiguous blocks that have not been allocated, and to determine if said one or more contiguous blocks define a dimension that is at least as large as said characteristic dimension.

Claim 39

The system of claim 37 wherein said allocator comprises a deallocator for freeing a contiguous portion of said virtual address space, said deallocator using said lists of records to identify at least one segment that contains at least some of said virtual address space to be freed, and, to access an entry of said map that is associated with said segment to identify contiguous elements that are associated with the blocks that comprise the contiguous portion of said virtual address space to be freed, said deallocator further causing each one of said identified contiguous elements to indicate that its associated block has not been allocated to store array data when said contiguous portion of said virtual address space has been freed, and said deallocator further updating one or more records that identify one or more segments that correspond to the entries in the map that contain said identified contiguous elements to indicate that space in said segments has been deallocated.

Claim 40

A process for allocating virtual address space for array data to be stored in a virtual memory, an attribute of said array being a dimension along an array direction; the process comprising the steps of: associating segments of said virtual address space with predetermined dimensions of array data in a table, and using said table to identify a contiguous portion of said virtual address space for said array data to be store.

Claim 41

A process for allocating virtual address space for array data to be stored in a virtual memory, an attribute of said array being a dimension along an array direction; the process comprising the steps of: associating segments of said virtual address space with predetermined dimensions of array data in a table, and using said table to identify a contiguous portion of said virtual address space for said array data to be store.

Claim 42

The process of claim 39 wherein said array data to be stored has a characteristic one of said predetermined dimensions, said segments being contiguous within said virtual address space and each said segment comprising a predetermined number of contiguous blocks for storing array data.

Claim 43

The process of claim 40 wherein said step of associating comprises a step of establishing lists of records for segments that have been at least partially allocated to store array data, each list being associated with a different predetermined dimension, and each record in each list being associated with a segment which has been at least partially allocated to store array data having the array data dimension associated with said list and identifying another record in said list.

Claim 44

The process of claim 41 wherein said step of associating further includes a step of establishing a list of records for segments that have not been allocated to store array data.

Claim 45

The process of claim 42 wherein said step of using comprises a step of identifying from said lists of records segments that have been at least partially allocated to store array data having said characteristic dimension or that have not been allocated to store array data to identify one or more candidate segments for storing said array data.

Claim 46

The process of claim 43 further comprising steps of: maintaining a map that identifies, for each said segment, which portions of said segment have been allocated to store array data, and providing an entry in said map associated with each said segment and a plurality of elements in each entry associated with the contiguous blocks in the corresponding segment, each element indicating whether its associated block has been allocated to store array data.

Claim 47

The process of claim 44 wherein said step of using further comprises a step of testing the elements of the map entries that correspond to said candidate segments to identify one or more contiguous elements associated with one or more contiguous blocks that have not been allocated, and determining if said one or more contiguous blocks define a dimension that is at least as large as said characteristic dimension.

Claim 48

The process of claim 45 further comprising a step of freeing a contiguous portion of said virtual address space, said freeing step comprising steps of: using said lists of records to identify at least one segment that contains at least some of said virtual address space to be freed, and accessing the entry of said map that is associated with said at least one segment to identify contiguous elements that are associated with the blocks that comprises the contiguous portion of said virtual address space to be freed, causing each one of said identified contiguous elements to indicate that its associated block has not been allocated to store array data when said contiguous portion of said virtual address spaced has been freed, and updating one or more records that identify one or more segments that correspond to the entries in the map that contain said identified contiguous elements to indicate that space in said one or more segments has been deallocated.