Maoni Stephens et al.Download PDFPatent Trials and Appeals BoardApr 8, 202013269634 - (D) (P.T.A.B. Apr. 8, 2020) Copy Citation UNITED STATES PATENT AND TRADEMARK OFFICE UNITED STATES DEPARTMENT OF COMMERCE United States Patent and Trademark Office Address: COMMISSIONER FOR PATENTS P.O. Box 1450 Alexandria, Virginia 22313-1450 www.uspto.gov APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO. 13/269,634 10/10/2011 MAONI STEPHENS 333654.01 2983 69316 7590 04/08/2020 MICROSOFT CORPORATION ONE MICROSOFT WAY REDMOND, WA 98052 EXAMINER ROLAND, GRISELLE CORBO ART UNIT PAPER NUMBER 2158 NOTIFICATION DATE DELIVERY MODE 04/08/2020 ELECTRONIC Please find below and/or attached an Office communication concerning this application or proceeding. The time period for reply, if any, is set in the attached communication. Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the following e-mail address(es): chriochs@microsoft.com usdocket@microsoft.com PTOL-90A (Rev. 04/07) UNITED STATES PATENT AND TRADEMARK OFFICE BEFORE THE PATENT TRIAL AND APPEAL BOARD Ex parte MAONI STEPHENS and PATRICK DUSSUD Appeal 2018-005982 Application 13/269,634 Technology Center 2100 Before JUSTIN BUSCH, BETH Z. SHAW, and SCOTT E. BAIN, Administrative Patent Judges. BAIN, Administrative Patent Judge. DECISION ON APPEAL Appellant1 appeals under 35 U.S.C. § 134(a) from the Examiner’s decision to reject claims 1–20, which constitute all claims pending in the application. We have jurisdiction under 35 U.S.C. § 6(b). We reverse. 1 We use the word Appellant to refer to “applicant” as defined in 37 C.F.R. § 1.42(a). Appellant identifies the real party in interest as Microsoft Technology Licensing, LLC. Appeal Br. 1. Appeal 2018-005982 Application 13/269,634 2 BACKGROUND The Claimed Invention The invention relates to memory storage techniques, and specifically, to minimizing computational overhead in certain “heap storage” techniques. Spec. ¶¶ 1–2. As described in the Specification, heap storage is a set of memory locations used by objects that are dynamically allocated during program execution. Id. ¶ 1. As a program executes, heap storage is allocated from free memory space, and released “explicitly” or “implicitly” when memory locations are no longer used. Id. When heap storage is released explicitly, “the memory locations are added to a pool of free memory space.” Id. Allocated heap storage that is no longer accessed by a program is called “garbage,” and “garbage collection” is the “process of reclaiming the memory locations” no longer accessed by the program. Id. According to the Specification, a potential drawback of heap storage is that garbage collection “adds considerable overhead to a program since the garbage collector has to keep track of the objects that are referenced and then has to release the unreferenced objects on the fly.” Id. ¶ 2. The present invention aims to “minimize the computational overhead of [the] garbage collector” in a heap storage arrangement, while sustaining the performance of the program. Id. Claims 1, 9, and 15 are independent. Claim 1 is representative of the invention and the subject matter in dispute, and reads as follows: 1. A computer-implemented method, comprising: storing onto a mark stack, by a first garbage collector thread, a partially-marked object reference having a pair of consecutive entries in the mark stack, one entry of the pair representing a parent object and a second entry of the pair Appeal 2018-005982 Application 13/269,634 3 representing a child object reference, the mark stack accessible by multiple garbage collector threads concurrently, the child object reference comprises a location of a reference of the parent object that has not been marked; searching the mark stack, by a second garbage collector thread, for a partially-marked object reference, the first garbage collector thread different from the second garbage collector thread; and stealing from the mark stack, by the second garbage collector thread, the partially-marked object reference by replacing the child object reference with a stolen value. Appeal Br. 13 (Claims Appendix) (emphases added). References The references relied upon by the Examiner are: Name Reference Date Flood et al. US 6,826,583 B1 Nov. 30, 2004 Ylonen US 2009/0327372 A1 Dec. 31, 2009 The Rejections on Appeal Claims 1–4, 6–12, 15, 16, and 20 stand rejected under pre-AIA 35 U.S.C. § 102 as being anticipated by Flood. Final Act. 3–13. Claims 5, 13, 14, and 17–19 stand rejected under pre-AIA 35 U.S.C. § 103 as being unpatentable over Flood and Ylonen. Final Act. 13–18. DISCUSSION We have reviewed the Examiner’s rejections in light of Appellant’s arguments presented in this appeal. Arguments which Appellant could have made but did not make in the Briefs are deemed to be waived. See 37 C.F.R. § 41.37(c)(1)(iv). On the record before us, we are persuaded of error. Rejection Under 35 U.S.C. § 102 Appeal 2018-005982 Application 13/269,634 4 Appellant argues the Examiner erred in finding Flood discloses a garbage collector thread storing onto a mark stack “a partially marked object reference” including a parent object reference and child object reference wherein the “child object reference comprises a location of a reference of the parent object that has not been marked,” as recited in claim 1. Appeal Br. 5–7 (emphases added); Reply Br. 2–5. Appellant contends that the passage of Flood cited by the Examiner, which describe storing references in a “work-to-be-completed queue,” disclose only objects that are marked, contrary to the foregoing limitations in claim 1. Appeal Br. 5–6. We agree. The Examiner relies on Flood’s disclosure of a garbage collector copying reachable objects in the “FROM” semi-space of the heap into the “TO” semi-space of the heap, and “updat[ing] the root pointer.” Ans. 2–5 (citing Flood 12:57–14:12, Figs. 5A, 5B, 5C, 5D). The Examiner finds: Asynchronously, thread 2 copies root C into “to” memory and updates the root pointer. Each root corresponds to a parent object of the pair. The threads scan each root and discover references to D (reference 45). The reference to object D is equivalent to the child object reference that have not been marked. Both speculatively allocating blocks D' and D" within their local allocation buffers (LABs). The "To" intermediate memory location contains partially marked objects because they have not yet all been copied. D' And D" were speculatively allocated. After the speculative allocation, threads t1 and t2 both read the word in D that would contain the forwarding pointer and observe that none is present. In order to resolve the contention between t1 and t2 for who is to copy D, both t1 and t2 attempt a CAS instruction to insert the forwarding pointer in D. Only one of these CAS instructions will succeed and only the thread performing the successful CAS will actually copy D. That thread copies D to its new location, and the other thread updates its references to that location. In this case, say that t1 does so first. Thread t1 copies D to D,' updates the reference in B' 55 and leaves behind in the location of D a forwarding Appeal 2018-005982 Application 13/269,634 5 pointer. With reference to FIGS. 5c and 5d, thread t2 is second to execute its CAS on D, but t2 finds that another thread has handled D since the newly written forwarding pointer in D will not match that in the CAS instruction executed by t2. However, t2's CAS operation returns the newly written forwarding points to D,' and, so, t2 updates the reference pointer 60 in C' to point to D' and de-allocates the block D" 49 that was previously allocated for copying D by t2. Thread t1 finds a reference 57 in 01 to object E. and copies E to E' again leaving a forwarding pointer in location E and updating the pointer in D' to point to E' 59. When Band C have been copied, to the "to" memory, they are considered partially marked objects because they are roots with references to other objects that have not yet been copied. Ans. 3–4 (sic.). We cannot discern, from the foregoing findings or elsewhere in the record, however, any disclosure of a child object that “comprises a location of a reference of the parent object that has not been marked,” as recited in claim 1 (emphasis added). As Appellant argues, the Examiner appears to equate an object that has not (yet) been copied with an “unmarked” reference. Reply Br. 3. Even if the foregoing objects are interpreted as “unmarked,” however, the Examiner does not explain how such objects include “a location of a reference of the parent object,” as recited in claim 1. Moreover, the passages of Flood cited by the Examiner describe “reachable objects,” which, as Appellant argues, cannot be the claimed unmarked references because they are “reclaimed and added to the pool of free memory space.” Reply Br. 4; Flood 3:35–38. As disclosed in Flood: mutator work threads share heap memory. At least a portion of this shared memory is partitioned into semi-spaces referred to herein as "from" and "to" spaces. Reachable objects (here defined to include any "work tasks" or "live objects, " etc.) are stored as they are 35 created by mutator threads in "from" space, and a later garbage collection cycle will transfer the Appeal 2018-005982 Application 13/269,634 6 reachable objects pointed to by a root source into "to" space .… Between any two garbage collection cycles, all objects are allocated in one semi-space ("from" space), leaving the other semi-space ("to" space) free. When the garbage-collection cycle occurs, objects identified as reachable are "evacuated," i.e., copied compactly into the "to" semi-space from the "from" semi-space, which is then considered free.…the threads. Contention is resolved by atomic instructions. The heap is broken into a young and an old generation where semi-space copying employing local allocation buffers is used to collect the reachable objects in the young section. Flood 3:31–38, 4:31–37 (emphases added), Abstract; Reply Br. 3–4. As Appellant argues, the Examiner has not sufficiently explained how the foregoing reachable object of flood can constitute an “unmarked reference” as recited in claim 1. For the foregoing reasons, we are persuaded of error regarding the anticipation rejection of claim 1. For the same reasons, we are persuaded of error regarding the rejection of independent claims 9 and 15, which include limitations commensurate in scope with the disputed limitation of claim 1, and dependent claims 2–4, 6–8, 10–12, 16, and 20. Accordingly, we do not sustain the anticipation rejection of claims 1–4, 6–12, 15, 16, and 20. Rejection Under 35 U.S.C. § 103 Remaining claims 5, 13, 14, and 17–19 all are dependent claims, and are rejected as obvious over the combination of Flood and Ylonen. The Examiner does not find that Ylonen (or its teachings in combination with Flood) cures the deficiencies regarding independent claims 1, 9, and 15, discussed above. Accordingly, for the same reasons as discussed above, we are persuaded of error as to the obviousness rejection. We, therefore, do not sustain the obviousness rejection. Appeal 2018-005982 Application 13/269,634 7 SUMMARY In summary: Claims Rejected 35 U.S.C. § Reference(s)/Basis Affirmed Reversed 1–4, 6–12, 15, 16, 20 102 Flood 1–4, 6–12, 15, 16, 20 5, 13, 14, 17–19 103 Flood, Ylonen 5, 13, 14, 17–19 Overall Outcome 1–20 DECISION We reverse the Examiner’s decision rejecting claims 1–20. REVERSED Copy with citationCopy as parenthetical citation