1/*
2 * Copyright (c) 2011 Apple Inc. All rights reserved.
3 *
4 * @APPLE_APACHE_LICENSE_HEADER_START@
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * @APPLE_APACHE_LICENSE_HEADER_END@
19 */
20/*
21    ZoneCollectors.cpp
22    Zone Scanning Algorithms
23    Copyright (c) 2009-2001 Apple Inc. All rights reserved.
24 */
25
26#include "ReferenceIterator.h"
27#include "Zone.h"
28
29namespace Auto {
30
31    // BitmapPendingStack uses the pending bitmap as its store.
32    template <typename ReferenceIterator> class BitmapPendingStack {
33    public:
34        ReferenceIterator *_scanner;
35        CollectionTimer *_collection_timer;
36        pthread_mutex_t _scan_mutex;
37        pthread_cond_t _scan_cond;
38        Region *_scan_region;
39        SubzoneRangeIterator _subzone_iterator;
40        Large *_scan_large;
41        usword_t _scanning_threads;
42        bool _pendedLargeBlock;
43        bool _pendedSubzoneBlock;
44
45        BitmapPendingStack() : _scanner(NULL), _collection_timer(NULL), _subzone_iterator(NULL), _scanning_threads(0), _pendedLargeBlock(false), _pendedSubzoneBlock(false)
46        {
47            pthread_mutex_init(&_scan_mutex, NULL);
48            pthread_cond_init(&_scan_cond, NULL);
49        }
50
51        const PendingStackHint hints() { return PendingStackIsFixedSize | PendingStackChecksPendingBitmap | PendingStackSupportsThreadedScan; }
52
53        void set_timer(CollectionTimer *timer) { _collection_timer = timer; }
54
55        void push(Subzone *subzone, usword_t q) {
56            if (!subzone->test_and_set_pending(q, false)) {
57                _pendedSubzoneBlock = true;
58                Subzone::PendingCountAccumulator *accumulator = (Subzone::PendingCountAccumulator *)subzone->region()->zone()->registered_thread().pending_count_accumulator();
59                if (accumulator)
60                    accumulator->pended_in_subzone(subzone);
61                else
62                    subzone->add_pending_count(1);
63            }
64        }
65
66        void push(Large *large) {
67            _pendedLargeBlock = true;
68            large->set_pending();
69        }
70
71        static bool mark(Subzone *subzone, usword_t q) { return subzone->test_and_set_mark(q); }
72        static bool mark(Large *large) { return large->test_and_set_mark(); }
73        bool is_marked(Subzone *subzone, usword_t q) { return subzone->is_marked(q); }
74        bool is_marked(Large *large) { return large->is_marked(); }
75
76        void visit(Zone *zone, Large *large) {
77            Subzone::PendingCountAccumulator info(zone->registered_thread());
78            CollectionTimer::ScanTimer timer;
79            if (_collection_timer) timer.start();
80            if (large->is_pending()) {
81                worker_print("scanning large %p\n", large);
82                large->clear_pending();
83                _scanner->scan(large);
84                zone->statistics().add_blocks_scanned(1);
85                zone->statistics().add_bytes_scanned(large->size());
86            }
87            if (_collection_timer) {
88                timer.stop();
89                _collection_timer->scan_timer().add_time(timer);
90            }
91        }
92
93        void visit(Zone *zone, Subzone *sz) {
94            usword_t blocks_scanned = 0;
95            usword_t bytes_scanned = 0;
96            Subzone::PendingCountAccumulator info(zone->registered_thread());
97            CollectionTimer::ScanTimer timer;
98            if (_collection_timer) timer.start();
99            worker_print("scanning subzone %p\n", sz);
100            int32_t scanned_count;
101            do {
102                Bitmap::AtomicCursor cursor = sz->pending_cursor();
103                scanned_count = 0;
104                usword_t q = cursor.next_set_bit();
105                while (q != (usword_t)-1) {
106                    if (!sz->is_free(q)) {
107                        _scanner->scan(sz, q);
108                        blocks_scanned++;
109                        bytes_scanned += sz->size(q);
110                    }
111                    scanned_count++;
112                    q = cursor.next_set_bit();
113                }
114                info.flush_count();
115            } while (sz->add_pending_count(-scanned_count) != 0);
116            if (_collection_timer) {
117                timer.stop();
118                _collection_timer->scan_timer().add_time(timer);
119            }
120            zone->statistics().add_blocks_scanned(blocks_scanned);
121            zone->statistics().add_bytes_scanned(bytes_scanned);
122        }
123
124        const inline bool visit_larges_concurrently()   const { return true; }
125
126        void scan(ReferenceIterator &scanner) {
127            _scanner = &scanner;
128            do {
129                _pendedSubzoneBlock = false;
130                _pendedLargeBlock = false;
131                visitAllocatedBlocks_concurrent(_scanner->zone(), *this);
132            } while (_pendedSubzoneBlock || _pendedLargeBlock);
133        }
134
135        template <typename U> struct rebind { typedef BitmapPendingStack<U> other; };
136    };
137
138    class PartialCollectionVisitor {
139    protected:
140        struct Configuration;
141        typedef ReferenceIterator<Configuration> PartialReferenceIterator;
142
143        struct Configuration {
144            typedef PartialCollectionVisitor ReferenceVisitor;
145            typedef BitmapPendingStack<PartialReferenceIterator> PendingStack;
146            typedef GenerationalScanningStrategy<PartialReferenceIterator> ScanningStrategy;
147        };
148
149    public:
150        void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {}
151        void visit(const ReferenceInfo &info, void **slot, Large *large) {}
152
153        void scan(Zone *zone, void *stack_bottom, CollectionTimer &timer) {
154            Configuration::PendingStack stack;
155            const bool should_enliven = true;
156            PartialReferenceIterator scanner(zone, *this, stack, stack_bottom, should_enliven, zone->repair_write_barrier());
157            if (timer.scan_timer_enabled())
158                stack.set_timer(&timer);
159            scanner.scan();
160        }
161    };
162
163    class FullCollectionVisitor {
164    protected:
165        struct Configuration;
166        typedef ReferenceIterator<Configuration> FullReferenceIterator;
167        struct Configuration {
168            typedef FullCollectionVisitor ReferenceVisitor;
169            typedef BitmapPendingStack<FullReferenceIterator> PendingStack;
170            typedef FullScanningStrategy<FullReferenceIterator> ScanningStrategy;
171        };
172    public:
173        void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {}
174        void visit(const ReferenceInfo &info, void **slot, Large *large) {}
175
176        void scan(Zone *zone, void *stack_bottom, CollectionTimer &timer) {
177            Configuration::PendingStack stack;
178            const bool should_enliven = true, dont_repair = false;
179            FullReferenceIterator scanner(zone, *this, stack, stack_bottom, should_enliven, dont_repair);
180            if (timer.scan_timer_enabled())
181                stack.set_timer(&timer);
182            scanner.scan();
183        }
184
185        const boolean_t keep_statistics() const { return true; }
186    };
187
188    //
189    // collect_partial
190    //
191    // Performs a partial (generational) collection.
192    //
193    void Zone::collect_partial(void *current_stack_bottom, CollectionTimer &timer) {
194        PartialCollectionVisitor visitor;
195        visitor.scan(this, current_stack_bottom, timer);
196    }
197
198    //
199    // collect_full
200    //
201    void Zone::collect_full(void *current_stack_bottom, CollectionTimer &timer) {
202        FullCollectionVisitor visitor;
203        visitor.scan(this, current_stack_bottom, timer);
204    }
205
206} // namespace Auto
207