Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 are currently pending for examination.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 2, 3, 8, 10, 11, 12, 17, 19, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Jacob (US 20190354472 A1) in view of Wang (US 20190173841 A1) in further view of Narad (US 8549256 B2).
As per claim 1, Jacob discloses:
receiving, by a first extended Berkeley packet filter (eBPF) program, a first entry based on an atomic operation, the first entry being from a number of entries in a free list that indicates available space in a buffer; identifying, based on the first entry, a pointer to the buffer, the pointer being associated with an allocation of the available space in the buffer based on the first entry, the allocation of the available space being to the first eBPF program ("Circular buffer 320 include entries for maintaining a freepointer linked list structure, with each entry pointing to available (free) locations (addresses) in the external or DDR memory 101. ", 0023 ; "The apparatus comprises: a circular buffer having entries for storing pointers to free memory locations in the memory system, the circular buffer maintaining a queue including a linked list of free memory pointers corresponding to available memory locations in the DRAM; a controller to receive requests from one or more processor cores of a multi-core processor, a request comprising one of: a request to receive a free memory location, or a request to release a freed memory location; and the controller removing of a stored memory pointer via a top of the queue for transmittal to a requesting processor core in response to the request to receive, or adding a memory pointer released from the processor core to the top of the queue in response to the request to release, the apparatus managing a sub-set of free memory pointers to the external memory system.", 0008 ; “A buffered free memory pointer architecture configured to manage memory, e.g., allocate and deallocate the free list locations of data structures in memory, and improve the performance of the computer when multiple requestors need these locations as a burst”, 0007 ; Examiner Note: available/free memory locations equate to available spaces in a buffer, and a program executing on a processor corresponds to an eBPF program)
Jacob discloses the above limitation of claim 1, but does not explicitly disclose the requesting program being an eBPF program, or executing said eBPF program.
However, Wang discloses:
executing, by a processing device, the first eBPF program with exclusive access to the allocation of the available space in the buffer during an execution instance of the first eBPF program. ("Within the kernel space of guest OS 222, eBPF instructions run in a virtual machine environment that interprets the eBPF code for virtual CPUs 225 to enable them to perform the eBPF instructions. For example, the virtual machine provides registers, stack space, a program counter, and helper functions. The eBPF virtual machine provides a completely isolated environment for its bytecode running inside. As a result, an eBPF program, for example, may not arbitrarily call other kernel functions or gain access into memory outside eBPF kernel module 330.", 0038 ; “The hardware abstraction layer thus provides benefits of resource isolation and allocation among the virtual computing instances.”, 0058 ; Examiner Note: eBPF’s not being able to access memory outside of the virtual machine environment which they are running within equates to each eBPF instance having exclusive access to allocated available space)
The system of Jacob in view of Wang would be capable of allocating exclusive access to available spaces in a buffer to eBPF instances. It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob with those of Wang in order to provide the benefits of resource isolation and allocation among eBPFs running in virtual environments on the same CPU (Wang, [0058]).
Jacob in view of Wang discloses the above limitations of claim 1, but does not explicitly disclose the operations associated with receiving and releasing memory being atomic.
However, Narad discloses:
Receiving…a first entry based on an atomic operation (“A simple and lightweight mechanism for buffer allocation and recovery is provided. Hardware support for atomic enqueue and dequeue of buffers through producer-consumer rings, along with detection of completed (retired) buffers enables buffer management in only a few instructions.”, col.8, lines 64-67)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob in view of Wang with those of Narad in order to provide a simple and lightweight mechanism for buffer allocation and recovery (Narad, [col.8, lines 64-65])
As per claim 2, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1.
Furthermore, Narad discloses:
releasing, based on the atomic operation, the first entry to the free list after completion of the execution instance of the first eBPF program (“Hardware support for atomic enqueue and dequeue of buffers through producer-consumer rings, along with detection of completed (retired) buffers enables buffer management in only a few instructions. In the realtime executive loop run on the PP, a short section is devoted to reclaimation of free buffers into the free list from those rings which indicate to the PP that they have retired buffers available for recovery.”, col.8-9, lines 65-5)
the first entry being available to a second eBPF program based on the releasing of the first entry by the first eBPF program (“Atomic enqueueing by multiple sources is supported via writes to RTU[MTPROD] associated with that MAC's Transmit Ring.”, col.23, lines 33-34)
As per claim 3, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 2.
Furthermore, Narad discloses:
receiving, by the second eBPF program, the first entry from the free list after the releasing of the first entry to the free list by the first eBPF program. ("In one embodiment, the freepointer list cache 320 is configured as a circular queue 310 having entries 315 storing a set or sub-set of implicitly linked free memory locations corresponding to the free point linked list structure 125 in the external (e.g., DDR or DRAM) memory. In one embodiment, the queue 310 may further receive and contain entries of requested locations that have been freed or released by competing requestor engines 275.", 0027 ; "In one embodiment, requests 210 (e.g., messages or signals) from a processor engine are received at the freepointer manager via a bus interface element, e.g., a register 305, and processed by the double ended queue manager 350. Request signals received at the bus interface 305 include: 1) requests received indicating memory locations released by the competing requestor engine 275, e.g., a free memory pointer corresponding to a buffered location released by the engine; ", 0030 ; Examiner Note: the competing requestor engine corresponds to a first eBPF program, the requesting engine corresponds to a second eBPF program)
the first entry being received by the second eBPF program based on the atomic operation (“Atomic enqueueing by multiple sources is supported via writes to RTU[MTPROD] associated with that MAC's Transmit Ring.”, col.23, lines 33-34)
As per claim 8, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1.
Furthermore, Jacob discloses:
a second eBPF program that calls the free list executes on a same central processing unit (CPU) as the first eBPF program (“The apparatus comprises: a circular buffer having entries for storing pointers to free memory locations in the memory system, the circular buffer maintaining a queue including a linked list of free memory pointers corresponding to available memory locations in the DRAM; a controller to receive requests from one or more processor cores of a multi-core processor”, 0008 ; Examiner Note: the programs running on the respective processing cores correspond to eBPF programs)
The system of Jacob in view of Wang in further view of Booss would provide multiple eBPF programs capable of calling the freelist within the same computer (Wang, [0038]).
As per claim 10, it is a system claim (A system comprising: a processing device; and a memory to store instructions… (“ The processing unit(s) may be a single processor or a multi-core processor in different embodiments. The read-only-memory (ROM) may store static data and instructions that may be utilized by the processing unit(s) and other modules of the electronic system”, Wang, 0056)) comprising substantially the same limitations as claim 1, and as such, it is rejected for substantially the same reasons.
As per claim 11, it is a system claim comprising substantially the same limitations as claim 2, and as such, it is rejected for substantially the same reasons.
As per claim 12, it is system claim comprising substantially the same limitations as claim 3, and as such, it is rejected for substantially the same reasons.
As per claim 17, it is a system claim comprising substantially the same limitations as claim 8, and as such, it is rejected for substantially the same reasons.
As per claim 19, it is a non-transitory computer-readable storage medium (Wang: “described herein are embodiments of a non-transitory computer readable medium comprising instructions to be executed in a computer system”, 0011) claim comprising substantially the same limitations as claim 1, and as such, it is rejected for substantially the same reasons.
As per claim 20, it is a non-transitory computer-readable storage claim comprising substantially the same limitations as claim 2, and as such, it is rejected for substantially the same reasons.
Claims 4 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Jacob (US 20190354472 A1) in view of Wang (US 20190173841 A1) in further view of Narad (US 8549256 B2) in further view of Ylinen (US 20220083383 A1).
As per claim 4, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1, but does not disclose the allocation of available space in a buffer being based upon the eBPF map.
the allocation of the available space in the buffer is based on an eBPF map (“The initial amount of SGX EPC memory allocated to the container is written to the eBPF map to reflect the container's initial usage of this resource. The limit on the amount of SGX EPC memory that the container can use is written to the eBPF map as well.”, 0027 ; Examiner Note: SGX EPC memory corresponds to a buffer)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob in view of Wang in further view of Narad with those of Ylinen in order to provide a method for accounting of resources which is independent from the operating system kernel development cycle, operating system release schedules, and ecosystem adoption- resulting in earlier adoption of new hardware features, such as new processor features (Ylinen, [0012]).
As per claim 13, it is system claim comprising substantially the same limitations as claim 4, and as such, it is rejected for substantially the same reasons.
Claims 5, 6, 14, and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Jacob (US 20190354472 A1) in view of Wang (US 20190173841 A1) in further view of Narad (US 8549256 B2) in further view of Lee (US 20110016285 A1)
As per claim 5, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1, but does not disclose generating an array map and a stack map as described.
However, Lee discloses:
generating an array map and a stack map, the array map indicating a total number allocations of the buffer, the stack map indicating indices to the array map, wherein the first entry is associated with the stack map (“According to example embodiments, there may be provided a scratch pad memory management method, the method including dividing a scratch pad memory into a plurality of unit blocks, maintaining a memory allocation table in a main memory to manage the scratch pad memory, and managing the scratch pad memory by using the memory allocation table having indices respectively corresponding to the plurality of unit blocks.”, 0017 ; “the free memory area of the scratch pad memory may be classified based on a memory size and may be managed by a free list.”, 0045 ; Examiner Note: the memory allocation table equates to a stack map and unit blocks equate to allocations)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob in view of Wang in further view of Narad with those of Lee in order to provide a memory management system which increases the efficiency of the use of memory resources by applications (Lee, [0057]).
As per claim 6, Jacob in view of Wang in further view of Narad in further view of Lee fully discloses the limitations of claim 5.
However, Lee discloses:
the stack map is initialized to have a number of index values that is equal to the total number of allocations associated with the array map (see fig.2 ; “In this instance, the memory allocation table 210 may include a number of blocks corresponding to a number of the divided plurality of unit blocks, the indices of the divided plurality of unit blocks respectively correspond to indexes of the blocks included in the memory allocation table 210.”, 0040)
As per claim 14, it is system claim comprising substantially the same limitations as claim 5, and as such, it is rejected for substantially the same reasons.
As per claim 15, it is system claim comprising substantially the same limitations as claim 6, and as such, it is rejected for substantially the same reasons.
Claims 7 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Jacob (US 20190354472 A1) in view of Wang (US 20190173841 A1) in further view of Narad (US 8549256 B2) in further view of Singh (US 10133683 B1)
As per claim 7, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1, but does not disclose the number of entries in the free list being pushed to the free list and popped from the free list using an atomic procedure.
However, Singh discloses:
the number of entries in the free list is pushed to the free list and popped from the free list using an atomic procedure. (“The push and pop pointers 242 and 244 are used to keep track of the data filled in the buffer array 260 and the empty space available.”, col.6, lines 5-7)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob in view of Wang in further view of Narad with those of Singh in order to provide a memory allocator which is both thread-safe, faster than the existing technology, and consumes less primary input/output and gate area (Singh, [col.4, lines 20-30]).
As per claim 15, it is system claim comprising substantially the same limitations as claim 7, and as such, it is rejected for substantially the same reasons.
Claims 9 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Jacob (US 20190354472 A1) in view of Wang (US 20190173841 A1) in further view of Narad (US 8549256 B2) in further view of Gupta (US 20250068726 A1)
As per claim 9, Jacob in view of Wang in further view of Narad fully discloses the limitations of claim 1, but does not disclose kernel preemption being enabled during an execution instance of the first eBPF program.
However, Singh discloses:
kernel preemption is enabled during an execution instance of the first eBPF program (“ the determining step occurs in a modified system call table in a kernel of an operating system, the system call table running with preemption enabled”, 0012 ; “eBPF allows execution of sandboxed programs within the operating system which enables application developers to run eBPF programs to add additional capabilities to the operating system at runtime. The operating system then guarantees safety and execution efficiency as if natively compiled with the aid of a Just-In-Time (JIT) compiler and verification engine. System Tap itself has an option to insert custom code using a eBPF backend.”, 0054)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to combine the teachings of Jacob in view of Wang in further view of Narad with those of Gupta in order to manage the eBPF memory allocation with preemption enabled, thus allowing the use of semaphores, allocation of huge chunks of memory, making the code more dynamic, and protecting critical sections of code (Gupta, [0061]).
As per claim 15, it is system claim comprising substantially the same limitations as claim 7, and as such, it is rejected for substantially the same reasons.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Kelly (US 20240211305 A1) – discloses a system wherein trackable activity is performed by a process executing in an operating system of a computer, wherein detection is associated with an initial sequence number and initial message queue.
Kim (US 20080104357 A1) – discloses a generation unit that generates a free block list by arranging an entry including representative information of a group, of which free blocks adjacent to each other are grouped according to predetermined criteria, according to key values where the representative information are combined.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ROSS MICHAEL VINCENT whose telephone number is (703)756-1408. The examiner can normally be reached Mon-Fri 8:30AM-5:30PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, April Blair can be reached at (571) 270-1014. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/R.M.V./
Examiner, Art Unit 2196
/APRIL Y BLAIR/Supervisory Patent Examiner, Art Unit 2196
Prosecution Insights