1	/*
     2	Copyright 2014 The Perkeep Authors
     3	
     4	Licensed under the Apache License, Version 2.0 (the "License");
     5	you may not use this file except in compliance with the License.
     6	You may obtain a copy of the License at
     7	
     8	     http://www.apache.org/licenses/LICENSE-2.0
     9	
    10	Unless required by applicable law or agreed to in writing, software
    11	distributed under the License is distributed on an "AS IS" BASIS,
    12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	See the License for the specific language governing permissions and
    14	limitations under the License.
    15	*/
    16	
    17	// Package gc defines a generic garbage collector.
    18	package gc // import "perkeep.org/pkg/gc"
    19	
    20	import (
    21		"context"
    22		"errors"
    23		"fmt"
    24	
    25		"go4.org/syncutil"
    26	)
    27	
    28	const buffered = 32 // arbitrary
    29	
    30	// Item is something that exists that may or may not survive a GC collection.
    31	type Item interface{}
    32	
    33	// A Collector performs a garbage collection.
    34	type Collector struct {
    35		// World specifies a World that should be stopped before a
    36		// collection and started again after.
    37		World World
    38	
    39		Marker         Marker
    40		Roots          Enumerator
    41		Sweeper        Enumerator
    42		ItemEnumerator ItemEnumerator
    43		Deleter        Deleter
    44	}
    45	
    46	type Marker interface {
    47		// Mark marks that an item should exist.
    48		// It must be safe for calls from concurrent goroutines.
    49		Mark(Item) error
    50	
    51		// IsMarked returns whether the item is marked.
    52		// It must be safe for calls from concurrent goroutines.
    53		IsMarked(Item) (bool, error)
    54	}
    55	
    56	// World defines the thing that should be stopped before GC and started after.
    57	type World interface {
    58		Stop() error
    59		Start() error
    60	}
    61	
    62	type Deleter interface {
    63		// Delete deletes an item that was deemed unreachable via
    64		// the garbage collector.
    65		// It must be safe for calls from concurrent goroutines.
    66		Delete(Item) error
    67	}
    68	
    69	// Enumerator enumerates items.
    70	type Enumerator interface {
    71		// Enumerate enumerates items (which items depends on usage)
    72		// and sends them to the provided channel. Regardless of return
    73		// value, the channel should be closed.
    74		//
    75		// If the provided context is closed, Enumerate should return
    76		// with an error (typically context.Canceled)
    77		Enumerate(context.Context, chan<- Item) error
    78	}
    79	
    80	// ItemEnumerator enumerates all the edges out from an item.
    81	type ItemEnumerator interface {
    82		// EnumerateItme is like Enuerator's Enumerate, but specific
    83		// to the provided item.
    84		EnumerateItem(context.Context, Item, chan<- Item) error
    85	}
    86	
    87	// ctx will be canceled on failure
    88	func (c *Collector) markItem(ctx context.Context, it Item, isRoot bool) error {
    89		if !isRoot {
    90			marked, err := c.Marker.IsMarked(it)
    91			if err != nil {
    92				return err
    93			}
    94			if marked {
    95				return nil
    96			}
    97		}
    98		if err := c.Marker.Mark(it); err != nil {
    99			return err
   100		}
   101	
   102		// FIXME(tgulacsi): is it a problem that we cannot cancel the parent?
   103		ctx, cancel := context.WithCancel(ctx)
   104		defer cancel()
   105	
   106		ch := make(chan Item, buffered)
   107		var grp syncutil.Group
   108		grp.Go(func() error {
   109			return c.ItemEnumerator.EnumerateItem(ctx, it, ch)
   110		})
   111		grp.Go(func() error {
   112			for it := range ch {
   113				if err := c.markItem(ctx, it, false); err != nil {
   114					return err
   115				}
   116			}
   117			return nil
   118		})
   119		return grp.Err()
   120	}
   121	
   122	// Collect performs a garbage collection.
   123	func (c *Collector) Collect(ctx context.Context) (err error) {
   124		if c.World == nil {
   125			return errors.New("no World")
   126		}
   127		if c.Marker == nil {
   128			return errors.New("no Marker")
   129		}
   130		if c.Roots == nil {
   131			return errors.New("no Roots")
   132		}
   133		if c.Sweeper == nil {
   134			return errors.New("no Sweeper")
   135		}
   136		if c.ItemEnumerator == nil {
   137			return errors.New("no ItemEnumerator")
   138		}
   139		if c.Deleter == nil {
   140			return errors.New("no Deleter")
   141		}
   142		if err := c.World.Stop(); err != nil {
   143			return err
   144		}
   145		defer func() {
   146			startErr := c.World.Start()
   147			if err == nil {
   148				err = startErr
   149			}
   150		}()
   151	
   152		// Mark.
   153		roots := make(chan Item, buffered)
   154		markCtx, cancelMark := context.WithCancel(ctx)
   155		var marker syncutil.Group
   156		marker.Go(func() error {
   157			defer cancelMark()
   158			for it := range roots {
   159				if err := c.markItem(markCtx, it, true); err != nil {
   160					return err
   161				}
   162			}
   163			return nil
   164		})
   165		marker.Go(func() error {
   166			return c.Roots.Enumerate(markCtx, roots)
   167		})
   168		if err := marker.Err(); err != nil {
   169			return fmt.Errorf("Mark failure: %v", err)
   170		}
   171	
   172		// Sweep.
   173		all := make(chan Item, buffered)
   174		sweepCtx, cancelSweep := context.WithCancel(ctx)
   175		var sweeper syncutil.Group
   176		sweeper.Go(func() error {
   177			return c.Sweeper.Enumerate(sweepCtx, all)
   178		})
   179		sweeper.Go(func() error {
   180			defer cancelSweep()
   181			for it := range all {
   182				ok, err := c.Marker.IsMarked(it)
   183				if err != nil {
   184					return err
   185				}
   186				if !ok {
   187					if err := c.Deleter.Delete(it); err != nil {
   188						return err
   189					}
   190				}
   191			}
   192			return nil
   193		})
   194		if err := sweeper.Err(); err != nil {
   195			return fmt.Errorf("Sweep failure: %v", err)
   196		}
   197		return nil
   198	}