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    WriteBarrier.cpp
22    Write Barrier for Generational GC
23    Copyright (c) 2004-2011 Apple Inc. All rights reserved.
24 */
25
26#include "Configuration.h"
27#include "Definitions.h"
28#include "Range.h"
29#include "WriteBarrier.h"
30#include "Zone.h"
31
32
33namespace Auto {
34
35    //----- WriteBarrier -----//
36
37
38    //
39    // scan_marked_ranges
40    //
41    // Scan ranges in block that are marked in the write barrier.
42    //
43    void WriteBarrier::scan_marked_ranges(void *address, const usword_t size, write_barrier_scanner_t scanner) {
44        // determine the end address
45        void *end = displace(address, size);
46        // determine the last used address
47        void *last = displace(address, size - 1);
48        // get the write barrier index for the begining of the block
49        usword_t i = card_index(address);
50        // get the write barrier index for the end of the block
51        const usword_t j = card_index(last);
52
53        Range sub_range;
54        while (true) {
55            // skip over unmarked ranges
56            for ( ; i <= j && !is_card_marked(i); i++) {}
57
58            // if no marks then we are done
59            if (i > j) break;
60
61            // scan the marks
62            usword_t k = i;
63            for ( ; i <= j && is_card_marked(i); i++) {}
64
65            // set up the begin and end of the marked range
66            void *range_begin = card_address(k);
67            void *range_end = card_address(i);
68
69            // truncate the range to reflect address range
70            if (range_begin < address) range_begin = address;
71            if (range_end > end) range_end = end;
72
73            // scan range
74            sub_range.set_range(range_begin, range_end);
75            scanner(sub_range, this);
76        }
77    }
78
79#ifndef __BLOCKS__
80    class write_barrier_scanner_helper : public WriteBarrier::write_barrier_scanner {
81        void (*_scanner) (Range&, WriteBarrier*, void*);
82        void *_arg;
83    public:
84        write_barrier_scanner_helper(void (*scanner) (const Range&, WriteBarrier*, void*), void *arg) : _scanner(scanner), _arg(arg) {}
85        virtual void operator() (const Range &range, WriteBarrier *wb) { _scanner(range, wb, _arg); }
86    };
87#endif
88
89    void WriteBarrier::scan_marked_ranges(void *address, const usword_t size, void (*scanner) (const Range&, WriteBarrier*, void*), void *arg) {
90#ifdef __BLOCKS__
91        scan_marked_ranges(address, size, ^(const Range &range, WriteBarrier *wb) { scanner(range, wb, arg); });
92#else
93        write_barrier_scanner_helper helper(scanner, arg);
94        scan_marked_ranges(address, size, helper);
95#endif
96    }
97
98    bool WriteBarrier::range_has_marked_cards(void *address, const usword_t size) {
99        void *last = displace(address, size - 1);
100        // get the write barrier index for the begining of the block
101        usword_t i = card_index(address);
102        // get the write barrier index for the end of the block
103        const usword_t j = card_index(last);
104        while (i <= j) if (is_card_marked(i++)) return true;
105        return false;
106    }
107
108    inline bool compare_and_swap(unsigned char *card, unsigned char old_value, unsigned char new_value) {
109#if defined(__arm__)
110        // <rdar://problem/7001590> FIXME:  use LDREX/STREX.
111        if (*card == old_value) {
112            *card = new_value;
113            return true;
114        }
115        return false;
116#else
117        return __sync_bool_compare_and_swap(card, old_value, new_value);
118#endif
119    }
120
121    // this should only called from Zone::mark_write_barriers_untouched().
122    usword_t WriteBarrier::mark_cards_untouched() {
123        usword_t count = 0;
124        for (unsigned char *card = (unsigned char*)address() + _protect, *limit = (unsigned char *)end(); card != limit; ++card) {
125            if (*card != card_unmarked) {
126                if (compare_and_swap(card, (unsigned char)card_marked, (unsigned char)card_marked_untouched))
127                    ++count;
128            }
129        }
130        return count;
131    }
132
133    // this should only called from Zone::clear_untouched_write_barriers().
134    usword_t WriteBarrier::clear_untouched_cards() {
135        usword_t count = 0;
136        for (unsigned char *card = (unsigned char*)address() + _protect, *limit = (unsigned char *)end(); card != limit; ++card) {
137            if (*card == card_marked_untouched) {
138                if (compare_and_swap(card, (unsigned char)card_marked_untouched, (unsigned char)card_unmarked))
139                    ++count;
140            }
141        }
142        return count;
143    }
144};
145