Patent ID: 6314436
Filing Date: 2001-11-06
Classification: G06F,Y10S

Abstract:
A marking method for traversing data structures formed of data objects linked by identifying pointers in a contiguous memory, preparatory to garbage collection of unmarked data objects, the method comprising the steps of:a) for a selected root object, traversing the pointers carried thereby to determine the objects linked to the root object;b) entering references to each object newly determined by the preceding step to a fixed size marking structure; andc) traversing pointers to determine further objects linked to those identified by the previous step;wherein steps b) and c) are repeated until the marking structure is full, following which the objects identified therein are marked, then the memory is scanned to locate any further objects linked to those already marked, characterised in that the contiguous memory is divided into a plurality of discrete pages, steps b) and c) are restricted to those objects within the same page as the root object, and for any linked object of that page, an identifier for that page is instead stored at step b), and wherein the method further comprises generating, for each page, an indication of the extent of coverage of that page by located data objects, and the scanning of the memory to locate any further objects linked to those already marked is performed only for those covered areas within the page identified by the identifier.