Method and apparatus for allocating and de-allocating consecutive blocks of memory in background memory management
First Claim
1. A system for allocating storage of incoming data packets into a memory of a packet processor, comprising:
- a first facility mapping a first block of memory of a fixed block size in bytes into an ordered plurality of atomic pages comprising each a fixed byte size;
a second facility mapping the same block of memory into ordered virtual pages of different sizes, ranging from a smaller virtual page size equal to the atomic page size up to a larger virtual page size equal to the fixed block size;
a third facility to allocate virtual pages as unavailable for storage or de-allocate virtual pages as available for storage;
a fourth facility to receive a data packet, ascertain packet size for the received packet, and to determine fit by checking allocation state for virtual pages of a smallest size that is equal to or larger than the packet size, then allocation state for next larger virtual pages, and so on, until a de-allocated, available virtual page is found; and
a fifth facility to select a virtual page to store the packet, and to update and mark associated atomic pages in the selected virtual page as available or unavailable for storage, in an ordered manner;
characterized in that, after each selection by the fifth facility, state of all atomic and virtual pages is updated.
6 Assignments
0 Petitions
Accused Products
Abstract
A system for allocating storage of incoming data packets into a memory of a packet processor has a first facility mapping a first block of memory of a fixed block size in bytes into an ordered plurality of atomic pages comprising each a fixed byte size, a second facility mapping the same block of memory into ordered virtual pages of different sizes, ranging from a smaller virtual page size equal to the atomic page size up to a larger virtual page size equal to the fixed block size, a third facility to allocate virtual pages as unavailable for storage or de-allocate virtual pages as available for storage, a fourth facility to receive a data packet, ascertain packet size for the received packet, and to determine fit by checking allocation state for virtual pages of a smallest size that is equal to or larger than the packet size, then allocation state for next larger virtual pages, and so on, until a de-allocated, available virtual page is found; and a fifth facility to select a virtual page to store the packet, and to update and mark associated atomic pages in the selected virtual page as available or unavailable for storage, in an ordered manner. The system is characterized in that, after each selection by the fifth facility, state of all atomic and virtual pages is updated.
-
Citations
23 Claims
-
1. A system for allocating storage of incoming data packets into a memory of a packet processor, comprising:
-
a first facility mapping a first block of memory of a fixed block size in bytes into an ordered plurality of atomic pages comprising each a fixed byte size;
a second facility mapping the same block of memory into ordered virtual pages of different sizes, ranging from a smaller virtual page size equal to the atomic page size up to a larger virtual page size equal to the fixed block size;
a third facility to allocate virtual pages as unavailable for storage or de-allocate virtual pages as available for storage;
a fourth facility to receive a data packet, ascertain packet size for the received packet, and to determine fit by checking allocation state for virtual pages of a smallest size that is equal to or larger than the packet size, then allocation state for next larger virtual pages, and so on, until a de-allocated, available virtual page is found; and
a fifth facility to select a virtual page to store the packet, and to update and mark associated atomic pages in the selected virtual page as available or unavailable for storage, in an ordered manner;
characterized in that, after each selection by the fifth facility, state of all atomic and virtual pages is updated. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A data packet router comprising:
-
external ports to receive and send data packets from and to neighboring connected routers; and
a packet processor having an on-board memory, and comprising a system for allocating storage of data packets in the on-board memory, the system having a first facility mapping a first block of memory of a fixed block size in bytes into an ordered plurality of atomic pages comprising each a fixed byte size, a second facility mapping the same block of memory into ordered virtual pages of different sizes, ranging from a smaller virtual page size equal to the atomic page size up to a larger virtual page size equal to the fixed block size, a third facility to allocate virtual pages as unavailable for storage or de-allocate virtual pages as available for storage, a fourth facility to receive a data packet, ascertain packet size for the received packet, and to determine fit by checking allocation state for virtual pages of a smallest size that is equal to or larger than the packet size, then allocation state for next larger virtual pages, and so on, until a de-allocated, available virtual page is found, and a fifth facility to select a virtual page to store the packet, and to update and mark associated atomic pages in the selected virtual page in an ordered manner. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 23)
-
-
17. A method for allocating storage of data packets in a memory of a packet processor, comprising the steps of:
-
(a) mapping, by a first facility, a first block of memory of a fixed block size in bytes into an ordered plurality of atomic pages comprising each a fixed byte size;
(b) mapping, by a second facility, the same block of memory into ordered virtual pages of different sizes, ranging from a smaller virtual page size equal to the atomic page size up to a larger virtual page size equal to the fixed block size;
(c) allocating, by a third facility, virtual pages as unavailable for storage or de-allocating virtual pages as available for storage;
(d) receiving a data packet by a fourth facility, ascertaining packet size for the received packet, and determining fit by checking allocation state for virtual pages of a smallest size that is equal to or larger than the packet size, then allocation state for next larger virtual pages, and so on, until a de-allocated, available virtual page is found; and
(e) selecting a virtual page by a fifth facility, to store the packet, and updating and marking associated atomic pages in the selected virtual page in an ordered manner.
-
Specification